An efficient algorithm for enumerating chordal bipartite induced subgraphs in sparse graphs

DOI10.1007/978-3-030-25005-8_28OpenAlexW3098933002MaRDI QIDQ2301754FDOQ2301754

Authors: Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura 

Publication date: 25 February 2020

Full work available at URL: https://arxiv.org/abs/1903.02161

Recommendations

• Efficient enumeration of bipartite subgraphs in graphs
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Efficient enumeration of subgraphs and induced subgraphs with bounded girth
• Approximating the sparsest \(k\)-subgraph in chordal graphs
• Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
• Finding bipartite subgraphs efficiently
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Efficient enumeration of maximal induced bicliques

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Discrete mathematics in relation to computer science (68Rxx)

Cited In (2)

• Approximating the \textsc{Sparsest} \(k\)-\textsc{Subgraph} in chordal graphs
• Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution

This page was built for publication: An efficient algorithm for enumerating chordal bipartite induced subgraphs in sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301754)