@techreport{oai:ipsj.ixsq.nii.ac.jp:00193956,
 author = {Kazuhiro, Kurita and Kunihiro, Wasa and Takeaki, Uno and Hiroki, Arimura and Kazuhiro, Kurita and Kunihiro, Wasa and Takeaki, Uno and Hiroki, Arimura},
 issue = {9},
 month = {Jan},
 note = {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., 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.},
 title = {An Efficient Algorithm for Enumerating Chordal Bipartite Induced Subgraphs in Graphs},
 year = {2019}
}