The clique-separator graph for chordal graphs

DOI10.1016/j.dam.2009.02.006zbMath1173.05036OpenAlexW1964882757MaRDI QIDQ1026133

Louis Ibarra

Publication date: 24 June 2009

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

Full work available at URL: https://doi.org/10.1016/j.dam.2009.02.006

zbMATH Keywords

split graphchordal graphinterval graphclique tree

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (21)

Signed graphs and the freeness of the Weyl subarrangements of type \(B_\ell\) ⋮ Component-cardinality-constrained critical node problem in graphs ⋮ Computing the clique-separator graph for an interval graph in linear time ⋮ Towards a characterization of leaf powers by clique arrangements ⋮ Resource allocation with time intervals ⋮ An efficient algorithm for counting Markov equivalent DAGs ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Computing role assignments of proper interval graphs in polynomial time ⋮ A fully dynamic graph algorithm for recognizing interval graphs ⋮ An efficient representation of chordal graphs ⋮ Induced subgraph isomorphism on proper interval and bipartite permutation graphs ⋮ Characterizing and computing the structure of clique intersections in strongly chordal graphs ⋮ Computing Role Assignments of Proper Interval Graphs in Polynomial Time ⋮ Intersection graphs of non-crossing paths ⋮ A simple algorithm to find Hamiltonian cycles in proper interval graphs ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ Unnamed Item ⋮ A UNIFIED FRAMEWORK FOR BI(TRI)CONNECTIVITY AND CHORDAL AUGMENTATION ⋮ Finding a Maximum-Weight Convex Set in a Chordal Graph ⋮ Clique partitioning with value-monotone submodular cost

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• Intersection graphs of paths in a tree
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Counting clique trees and computing perfect elimination schemes in parallel
• A characterisation of rigid circuit graphs
• Algorithmic graph theory and perfect graphs
• Incidence matrices and interval graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• A Fully Dynamic Algorithm for Recognizing and Representing Proper Interval Graphs
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Fast Algorithm for Reordering Sparse Matrices for Parallel Factorization
• A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
• The NP-completeness column: an ongoing guide
• On the tree representation of chordal graphs
• Representations of chordal graphs as subtrees of a tree
• Power of Natural Semijoins
• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Algorithms and Computation

This page was built for publication: The clique-separator graph for chordal graphs