| Item type |
SIG Technical Reports(1) |
| 公開日 |
2019-01-22 |
| タイトル |
|
|
タイトル |
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Graphs |
| タイトル |
|
|
言語 |
en |
|
タイトル |
An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Graphs |
| 言語 |
|
|
言語 |
eng |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
Hokkaido University |
| 著者所属 |
|
|
|
National Institute of Informatics |
| 著者所属 |
|
|
|
National Institute of Informatics |
| 著者所属 |
|
|
|
Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
Hokkaido University |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
National Institute of Informatics |
| 著者所属(英) |
|
|
|
en |
|
|
Hokkaido University |
| 著者名 |
Kazuhiro, Kurita
Kunihiro, Wasa
Takeaki, Uno
Hiroki, Arimura
|
| 著者名(英) |
Kazuhiro, Kurita
Kunihiro, Wasa
Takeaki, Uno
Hiroki, Arimura
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
In this paper, we propose a characterization of chordal bipartite graphs and an efficient enumeration algorithm for chordal bipartite induced subgraphs. A chordal bipartite graph is a bipartite graph without induced cycles with length six or more. It is known that chordal bipartite graphs have several characterizations. One of them is as follows: A bipartite graph B is chordal bipartite if and only if a hypergraph corresponding to B is β-acyclic. By using the characterization of β-acyclic hypergraphs, we show that a graph is chordal bipartite if and only if it has a special vertex elimination ordering. We call this vertex ordering chordal bipartite elimination ordering (CBEO). Moreover, we propose an algorithm ECB which enumerates all chordal bipartite induced subgraphs in O (ktΔ²) time per solution, where, k is the degeneracy, t is the maximum size of Kt,t as a subgraph, and Δ is the degree. |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
In this paper, we propose a characterization of chordal bipartite graphs and an efficient enumeration algorithm for chordal bipartite induced subgraphs. A chordal bipartite graph is a bipartite graph without induced cycles with length six or more. It is known that chordal bipartite graphs have several characterizations. One of them is as follows: A bipartite graph B is chordal bipartite if and only if a hypergraph corresponding to B is β-acyclic. By using the characterization of β-acyclic hypergraphs, we show that a graph is chordal bipartite if and only if it has a special vertex elimination ordering. We call this vertex ordering chordal bipartite elimination ordering (CBEO). Moreover, we propose an algorithm ECB which enumerates all chordal bipartite induced subgraphs in O (ktΔ²) time per solution, where, k is the degeneracy, t is the maximum size of Kt,t as a subgraph, and Δ is the degree. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2019-AL-171,
号 9,
p. 1-7,
発行日 2019-01-22
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL19171009.pdf (1.3 MB)
