Minimal vertex separators of chordal graphs

DOI10.1016/S0166-218X(98)00123-1zbMath0921.68064MaRDI QIDQ1281392

C. E. Veni Madhavan, P. Sreenivasa Kumar

Publication date: 29 September 1999

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

zbMATH Keywords

perfect graphsmaximum cardinality searchlexicographic breadth first scheme

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

A linear time algorithm to list the minimal separators of chordal graphs, Generating and characterizing the perfect elimination orderings of a chordal graph, Clique tree generalization and new subclasses of chordal graphs, Computing a clique tree with the algorithm maximal label search, Linearizing partial search orders, Some results on connected vertex separators, The firebreak problem, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Searching for better fill-in, One-phase algorithm for the determination of minimal vertex separators of chordal graphs, Efficiently enumerating minimal triangulations, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, Minimal separators in extended \(P_4\)-laden graphs, The square of a block graph, Euclidean Distance Matrices and Applications, Linear separation of connected dominating sets in graphs, Minimal separators in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msub><mml:mi>P</mml:mi><mml:mn>4</mml:mn></mml:msub></mml:math>-tidy graphs, Generalized chordality, vertex separators and hyperbolicity on graphs, k-separator chordal graphs: leafage and subfamilies, Linear-time algorithms for tree root problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On rigid circuit graphs
• A linear-time algorithm for isomorphism of a subclass of chordal graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• On the Desirability of Acyclic Database Schemes
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Scheduling Interval-Ordered Tasks
• Algorithmic Aspects of Vertex Elimination on Graphs