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

DOI10.1016/J.TCS.2018.08.009zbMath1437.05102OpenAlexW2886539986WikidataQ129409158 ScholiaQ129409158MaRDI QIDQ1985603

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

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 graphsgraph enumerationclique treespolynomial delay

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Maximum 4-degenerate subgraph of a planar graph
• Computational aspects of monotone dualization: a brief survey
• Large induced degenerate subgraphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Split Graphs Having Dilworth Number Two
• Algorithmic Aspects of Vertex Elimination on Graphs
• Finding a Maximum Induced Degenerate Subgraph Faster Than 2 n
• Enumerating and Generating Labeled k-degenerate Graphs
• Listing All Maximal Cliques in Large Sparse Real-World Graphs

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