Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
From MaRDI portal
Publication:1751087
DOI10.1007/s00453-017-0297-1zbMath1390.68344arXiv1404.3882OpenAlexW3022919855WikidataQ60488399 ScholiaQ60488399MaRDI QIDQ1751087
Mathieu Liedloff, Ioan Todinca, Fedor V. Fomin, Pedro Montealegre
Publication date: 23 May 2018
Published in: Algorithmica, Algorithm Theory – SWAT 2014 (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.3882
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items (16)
Iterated Type Partitions ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Treewidth and pathwidth parameterized by the vertex cover number ⋮ Finding optimal triangulations parameterized by edge clique cover ⋮ The use of a pruned modular decomposition for \textsc{maximum matching} algorithms on some graph classes ⋮ Finding a maximum minimal separator: graph classes and fixed-parameter tractability ⋮ Parameterized Algorithms for Parity Games ⋮ Maximum Minimal Vertex Cover Parameterized by Vertex Cover ⋮ Graph reconstruction in the congested clique ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ On structural parameterizations of Node Kayles ⋮ Unnamed Item ⋮ 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 ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Beyond Classes of Graphs with “Few” Minimal Separators: FPT Results Through Potential Maximal Cliques
Cites Work
- Unnamed Item
- Unnamed Item
- Sparsity. Graphs, structures, and algorithms
- On cutwidth parameterized by vertex cover
- Computing tree-depth faster than \(2^n\)
- Improved upper bounds for vertex cover
- On the complexity of computing treelength
- Computing the treewidth and the minimum fill-in with the modular decomposition
- Listing all potential maximal cliques of a graph
- Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
- Algorithmic meta-theorems for restrictions of treewidth
- Tree decompositions with small cost
- The complexity of first-order and monadic second-order logic revisited
- On the vertex ranking problem for trapezoid, circular-arc and other graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Treewidth computation and extremal combinatorics
- 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
- Treewidth and Pathwidth Parameterized by the Vertex Cover Number
- Parameterized Algorithms for Modular-Width
- Large Induced Subgraphs via Triangulations and CMSO
- Finding Induced Subgraphs via Minimal Triangulations
- Easy problems for tree-decomposable graphs
- Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
- Graph Layout Problems Parameterized by Vertex Cover
- Exact Algorithms for Treewidth and Minimum Fill-In
- A Faster Parameterized Algorithm for Treedepth
- Minimal Triangulation Algorithms for Perfect Phylogeny Problems
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Algorithms parameterized by vertex cover and modular width, through potential maximal cliques
