Minimal separators in extended \(P_4\)-laden graphs

DOI10.1016/j.dam.2012.01.025zbMath1254.05189OpenAlexW2075197346MaRDI QIDQ1759855

Vagner Pedrotti, Célia Picinin de Mello

Publication date: 22 November 2012

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

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

zbMATH Keywords

modular decompositionlinear-time algorithmsminimal separatorsprimeval decompositiongraphs with few \(P_{4}\)'s

Mathematics Subject Classification ID

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

Related Items (3)

Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem ⋮ Perfect matching cuts partitioning a graph into complementary subgraphs ⋮ PSPACE-completeness of two graph coloring games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Listing all the minimal separators of a 3-connected planar graph
• Minimal separators in \(P_4\)-sparse graphs
• Minimal vertex separators of chordal graphs
• Modular decomposition and transitive orientation
• \(P_{4}\)-laden graphs: A new class of brittle graphs
• Computing the treewidth and the minimum fill-in with the modular decomposition
• Listing all potential maximal cliques of a graph
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• A New Class of Brittle Graphs
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Complexity of Finding Embeddings in a k-Tree
• Computing the Minimum Fill-In is NP-Complete
• Listing all Minimal Separators of a Graph
• P-Components and the Homogeneous Decomposition of Graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH

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