Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques

DOI10.1007/978-3-662-53174-7_35zbMath1417.05222OpenAlexW2486778190MaRDI QIDQ2827832

Mathieu Liedloff, Pedro Montealegre, Ioan Todinca

Publication date: 21 October 2016

Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-53174-7_35

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (2)

Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

Cites Work

• Unnamed Item
• Unnamed Item
• Parameterized complexity of vertex deletion into perfect graph classes
• Graph minors. XX: Wagner's conjecture
• Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
• Chordal deletion is fixed-parameter tractable
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Upper bounds on the size of obstructions and intertwines
• A partial k-arboretum of graphs with bounded treewidth
• Listing all potential maximal cliques of a graph
• Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
• The complexity of first-order and monadic second-order logic revisited
• Independent packings in structured graphs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Treewidth and Minimum Fill-in: Grouping the Minimal Separators
• Fixed-Parameter Tractability of Treewidth and Pathwidth
• Large Induced Subgraphs via Triangulations and CMSO
• Finding Induced Subgraphs via Minimal Triangulations
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH

This page was built for publication: Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques