Algorithms parameterized by vertex cover and modular width, through potential maximal cliques

DOI10.1007/978-3-319-08404-6_16zbMath1390.68344DBLPconf/swat/FominLMT14arXiv1404.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

zbMATH Keywords

treewidthvertex coverpotential maximal cliquesparametrized algorithms

Mathematics Subject Classification ID

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