Minimal separators in extended \(P_4\)-laden graphs
From MaRDI portal
Publication:1759855
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
modular decompositionlinear-time algorithmsminimal separatorsprimeval decompositiongraphs with few \(P_{4}\)'s
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