Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph

DOI10.1016/J.TCS.2018.08.009MaRDI QIDQ1985603zbMATH OpenOpenAlexWikidataFDO

Authors Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa

Publication date 7 April 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2018.08.009

zbMATH Keywords

degeneracygraph algorithmschordal graphsclique treespolynomial delaygraph enumeration

Mathematics Subject Classification ID

Trees (05C05) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Enumeration in graph theory (05C30) Density (toughness, etc.) (05C42)

Recommendations

• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Efficient enumeration of induced subtrees in a K-degenerate graph
• An output sensitive algorithm for maximal clique enumeration in sparse graphs
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)

Cites work

• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 1796975 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Algorithmic Aspects of Vertex Elimination on Graphs
• Computational aspects of monotone dualization: a brief survey
• Efficient enumeration of induced subtrees in a K-degenerate graph
• Enumerating and generating labeled \(k\)-degenerate graphs
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Large induced degenerate subgraphs
• Listing all maximal cliques in large sparse real-world graphs
• Maximum 4-degenerate subgraph of a planar graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Sparsity. Graphs, structures, and algorithms
• Split Graphs Having Dilworth Number Two
• Sublinear-space bounded-delay enumeration for massive network analytics: maximal cliques
• The intersection graphs of subtrees in trees are exactly the chordal graphs

Cited in

(7)

• Enumerating and generating labeled \(k\)-degenerate graphs
• An efficient algorithm for enumerating induced subgraphs with bounded degeneracy
• Efficient enumeration of maximal split subgraphs and induced sub-cographs and related classes
• An efficient algorithm for enumerating chordal bipartite induced subgraphs in sparse graphs
• Finding a maximum induced degenerate subgraph faster than \(2^{n}\)
• Efficient enumeration of maximal \(k\)-degenerate subgraphs in a chordal graph
• Efficient enumeration of induced subtrees in a K-degenerate graph

This page was built for publication: Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph

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