A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph

DOI10.1016/j.ipl.2011.02.013zbMath1259.05158OpenAlexW2047092660MaRDI QIDQ1944936

Anne Berry, Romain Pogorelcnik

Publication date: 28 March 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2011.02.013

zbMATH Keywords

MCSgraph algorithmsmaximal cliqueminimal separatorLexBFSmoplex ordering

Mathematics Subject Classification ID

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

Related Items (8)

A linear time algorithm for maximal clique enumeration in large sparse graphs ⋮ Computing a clique tree with the algorithm maximal label search ⋮ Objective Bayesian Nets for Integrating Consistent Datasets ⋮ Minimum Average Distance Clique Trees ⋮ Organizing the atoms of the clique separator decomposition into an atom tree ⋮ Moplex orderings generated by the LexDFs algorithm ⋮ Latent association graph inference for binary transaction data ⋮ Linear separation of connected dominating sets in graphs

Cites Work

• Minimal vertex separators of chordal graphs
• Separability generalizes Dirac's theorem
• Graph extremities defined by search algorithms
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Unified View of Graph Searching
• Algorithmic Aspects of Vertex Elimination on Graphs
• Maximal Label Search Algorithms to Compute Perfect and Minimal Elimination Orderings
• Unnamed Item
• Unnamed Item

This page was built for publication: A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph