A linear time algorithm to list the minimal separators of chordal graphs

DOI10.1016/j.disc.2005.12.010zbMath1085.05058OpenAlexW2030330259MaRDI QIDQ819826

Fabrizio Grandoni, L. Sunil Chandran

Publication date: 29 March 2006

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

Full work available at URL: https://doi.org/10.1016/j.disc.2005.12.010

zbMATH Keywords

perfect elimination ordering

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Some results on connected vertex separators ⋮ One-phase algorithm for the determination of minimal vertex separators of chordal graphs ⋮ The square of a block graph ⋮ Linear separation of connected dominating sets in graphs ⋮ k-separator chordal graphs: leafage and subfamilies ⋮ Unnamed Item ⋮ Linear-time algorithms for tree root problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some aspects of perfect elimination orderings in chordal graphs
• Minimal vertex separators of chordal graphs
• Treewidth. Computations and approximations
• Efficient enumeration of all minimal separators in a graph
• Generating and characterizing the perfect elimination orderings of a chordal graph
• Finding all minimum-size separating vertex sets in a graph
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Computing the Minimum Fill-In is NP-Complete
• Algorithmic Aspects of Vertex Elimination on Graphs
• Efficient Algorithms for Listing Combinatorial Structures
• Listing all Minimal Separators of a Graph
• Treewidth and Pathwidth of Permutation Graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH

This page was built for publication: A linear time algorithm to list the minimal separators of chordal graphs