Minimal separators in \(P_4\)-sparse graphs

DOI10.1016/j.disc.2005.12.008zbMath1087.05055OpenAlexW2113407832MaRDI QIDQ819831

Leonidas Palios, Stavros D. Nikolopoulos

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.008

zbMATH Keywords

perfect graphscographs

Mathematics Subject Classification ID

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

Related Items (5)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ The \(k\)-hop connected dominating set problem: approximation and hardness ⋮ Some results on connected vertex separators ⋮ Minimal separators in extended \(P_4\)-laden 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A tree representation for \(P_ 4\)-sparse graphs
• On extended \(P_4\)-reducible and extended \(P_4\)-sparse graphs
• Linear time optimization algorithms for \(P_ 4\)-sparse graphs
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Efficient and Practical Algorithms for Sequential Modular Decomposition
• P₄-Reducible Graphs-Class of Uniquely Tree-Representable Graphs
• A Linear Recognition Algorithm for Cographs
• Recognizing $P_4 $-Sparse Graphs in Linear Time
• Perfect Elimination and Chordal Bipartite Graphs
• Graph Classes: A Survey
• Asteroidal Triple-Free Graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
• Algorithm Theory - SWAT 2004
• Graph-Theoretic Concepts in Computer Science

This page was built for publication: Minimal separators in \(P_4\)-sparse graphs