Clique tree generalization and new subclasses of chordal graphs

DOI10.1016/S0166-218X(00)00336-XMaRDI QIDQ1348383zbMATHOpenAlexWikidataFDO

Authors P. Sreenivasa Kumar, C. E. Veni Madhavan

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

clique treeschordal graphmaximal cliquesminimal vertex separatorsreduced clique hypergraph

Mathematics Subject Classification ID

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

Recommendations

• Reduced clique graphs of chordal graphs
• scientific article; zbMATH DE number 554762
• Strong clique trees, neighborhood trees, and strongly chordal graphs
• Non-inclusion and other subclasses of chordal graphs
• On the tree representation of chordal graphs

Cites work

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

Cited in

(24)

• An efficient representation of chordal graphs
• Chordal graphs and their clique graphs
• Block-indifference graphs: characterization, structural and spectral properties
• A new characterization of \(k\)-trees and some applications
• A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
• Graphs that have clique (partial) 2-trees
• A generalization of chordal graphs and the maximum clique problem
• Tree-structured graphs
• A linear-time algorithm for isomorphism of a subclass of chordal graphs
• Linear-time algorithms for tree root problems
• Non-inclusion and other subclasses of chordal graphs
• Intersection graphs of non-crossing paths
• A unified framework for bi(tri)connectivity and chordal augmentation
• A linear time recognition algorithm for proper interval graphs
• Two methods for the generation of chordal graphs
• \(k\)-separator chordal graphs: leafage and subfamilies
• Tree 3-spanners in 2-sep chordal graphs: characterization and algorithms
• Vulnerability of subclasses of chordal graphs
• Reduced clique graphs of chordal graphs
• Strictly interval graphs: characterization and linear time recognition
• Tree 3-Spanner in 2-sep Chordal Graphs: Characterization, Recognition, and Construction.
• scientific article; zbMATH DE number 2170436 (Why is no real title available?)
• Clique trees of infinite locally finite chordal graphs
• On basic chordal graphs and some of its subclasses

This page was built for publication: Clique tree generalization and new subclasses of chordal graphs

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