Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
From MaRDI portal
Publication:666659
DOI10.1007/s00453-018-0453-2zbMath1418.05120OpenAlexW2800920272MaRDI QIDQ666659
Pedro Montealegre, Mathieu Liedloff, Ioan Todinca
Publication date: 11 March 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-018-0453-2
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 (8)
Finding optimal triangulations parameterized by edge clique cover ⋮ Structural parameterizations with modulator oblivion ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A meta-theorem for distributed certification ⋮ Subexponential parameterized algorithms and kernelization on almost chordal graphs ⋮ A meta-theorem for distributed certification
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of vertex deletion into perfect graph classes
- The multivariate algorithmic revolution and beyond. Essays dedicated to Michael R. Fellows on the occasion of his 60th birthday
- 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
- Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
- Large Induced Subgraphs via Triangulations and CMSO
- Chordal Editing is Fixed-Parameter Tractable
- Finding Induced Subgraphs via Minimal Triangulations
- Exact Algorithms for Treewidth and Minimum Fill-In
- Algorithmic Aspects of Vertex Elimination on Graphs
- Minimum Fill-in on Circle and Circular-Arc Graphs
- Treewidth and Minimum Fill-in on d-Trapezoid Graphs
- Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
- GENERATING ALL THE MINIMAL SEPARATORS OF A GRAPH
- Parameterized and Exact Computation
This page was built for publication: Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
