Clique tree generalization and new subclasses of chordal graphs

DOI10.1016/S0166-218X(00)00336-XzbMath0999.05017OpenAlexW2087220179WikidataQ127664744 ScholiaQ127664744MaRDI QIDQ1348383

C. E. Veni Madhavan, P. Sreenivasa Kumar

Publication date: 15 May 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00336-x

zbMATH Keywords

chordal graphmaximal cliquesclique treesminimal vertex separatorsreduced clique hypergraph

Mathematics Subject Classification ID

Trees (05C05) Hypergraphs (05C65) Perfect graphs (05C17)

Related Items

Strictly interval graphs: characterization and linear time recognition, Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms, An efficient representation of chordal graphs, Two methods for the generation of chordal graphs, Vulnerability of subclasses of chordal graphs, A linear-time algorithm for isomorphism of a subclass of chordal graphs, Intersection graphs of non-crossing paths, Non-inclusion and other subclasses of chordal graphs, A linear time recognition algorithm for proper interval graphs, A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION, Block-indifference graphs: characterization, structural and spectral properties, k-separator chordal graphs: leafage and subfamilies, Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction., Linear-time algorithms for tree root problems

Cites Work

• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Separating subgraphs in k-trees: Cables and caterpillars
• A linear-time algorithm for isomorphism of a subclass of chordal graphs
• Counting clique trees and computing perfect elimination schemes in parallel
• Minimal vertex separators of chordal graphs
• A characterisation of rigid circuit graphs
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• On double and multiple interval graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Generating the maximum spanning trees of a weighted graph
• On the tree representation of chordal graphs
• Fast Parallel Algorithms for Chordal Graphs
• Power of Natural Semijoins
• Dominating Sets in Chordal Graphs
• Trees with Hamiltonian square