Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph
From MaRDI portal
Publication:1985603
DOI10.1016/j.tcs.2018.08.009zbMath1437.05102OpenAlexW2886539986MaRDI 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
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
