Enumeration of the perfect sequences of a chordal graph

DOI10.1016/j.tcs.2010.06.007zbMath1210.05061OpenAlexW2090244442MaRDI QIDQ708216

Yasuko Matsui, Ryuhei Uehara, Takeaki Uno

Publication date: 11 October 2010

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

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

zbMATH Keywords

enumerationchordal graphperfect sequenceclique tree

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items

Constant Time Enumeration by Amortization ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ Reduced clique graphs of chordal graphs ⋮ An efficient representation of chordal graphs ⋮ Bayesian networks: the minimal triangulations of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• On generating all maximal independent sets
• Efficient graph representations
• Dirac's theorem on chordal graphs and Alexander duality
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Algorithmic graph theory and perfect graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Algorithmic Aspects of Vertex Elimination on Graphs
• Topics in Intersection Graph Theory
• Graph Classes: A Survey