Algorithmic meta-theorems for restrictions of treewidth
From MaRDI portal
Publication:1759681
DOI10.1007/s00453-011-9554-xzbMath1252.68154OpenAlexW2142055019MaRDI QIDQ1759681
Publication date: 21 November 2012
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00453-011-9554-x
Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Decidability of theories and sets of sentences (03B25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (84)
The Micro-world of Cographs ⋮ Parameterized Complexity of Fair Feedback Vertex Set Problem ⋮ Parameterized complexity of locally minimal defensive alliances ⋮ The balanced satisfactory partition problem ⋮ The micro-world of cographs ⋮ Rainbow independent sets on dense graph classes ⋮ Hull number: \(P_5\)-free graphs and reduction rules ⋮ Between treewidth and clique-width ⋮ A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Target Set Selection in Dense Graph Classes ⋮ A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata ⋮ On the harmless set problem parameterized by treewidth ⋮ Parameterized complexity of immunization in the threshold model ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ Winner determination algorithms for graph games with matching structures ⋮ The graph motif problem parameterized by the structure of the input graph ⋮ Parameterized complexity of fair feedback vertex set problem ⋮ Parameterized complexity of fair deletion problems ⋮ Complexity and approximability of parameterized MAX-CSPs ⋮ Preprocessing subgraph and minor problems: when does a small vertex cover help? ⋮ Between Treewidth and Clique-Width ⋮ Deterministic Algorithms for the Independent Feedback Vertex Set Problem ⋮ Parameterized complexity of distance labeling and uniform channel assignment problems ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Grundy Distinguishes Treewidth from Pathwidth ⋮ Integer programming in parameterized complexity: five miniatures ⋮ A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\) ⋮ On the computational complexity of the bipartizing matching problem ⋮ The structural complexity landscape of finding balance-fair shortest paths ⋮ Complexity of finding maximum regular induced subgraphs with prescribed degree ⋮ Dynamic coloring on restricted graph classes ⋮ Parameterizing path partitions ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity ⋮ Immunization in the threshold model: a parameterized complexity study ⋮ Structural parameterization of cluster deletion ⋮ Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU ⋮ Computing densest \(k\)-subgraph with structural parameters ⋮ Parameterized (Approximate) Defective Coloring ⋮ Meta-kernelization with structural parameters ⋮ Grouped domination parameterized by vertex cover, twin cover, and beyond ⋮ Parameterized complexity of happy coloring problems ⋮ On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs ⋮ Parameterized complexity for iterated type partitions and modular-width ⋮ On structural parameterizations of star coloring ⋮ Critical properties of bipartite permutation graphs ⋮ Spanning trees with few branch vertices in graphs of bounded neighborhood diversity ⋮ A Survey on the Complexity of Flood-Filling Games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Extended MSO model checking via small vertex integrity ⋮ Parameterized Complexity of Safe Set ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Finer Tight Bounds for Coloring on Clique-Width ⋮ How Bad is the Freedom to Flood-It? ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs ⋮ The average cut-rank of graphs ⋮ The Small Set Vertex expansion problem ⋮ Integer Programming in Parameterized Complexity: Three Miniatures. ⋮ Refined notions of parameterized enumeration kernels with applications to matching cut enumeration ⋮ Algorithms parameterized by vertex cover and modular width, through potential maximal cliques ⋮ Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number ⋮ Parameterized algorithms for the happy set problem ⋮ Winner determination algorithms for graph games with matching structures ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph ⋮ Letter graphs and geometric grid classes of permutations: characterization and recognition ⋮ Partitioning graphs into induced subgraphs ⋮ Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs ⋮ Width, depth, and space: tradeoffs between branching and dynamic programming ⋮ Scattered Classes of Graphs ⋮ Parameterized complexity of satisfactory partition problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Independent set reconfiguration parameterized by modular-width ⋮ Subgraph isomorphism on graph classes that exclude a substructure ⋮ Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems ⋮ Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs ⋮ Evangelism in Social Networks ⋮ Unnamed Item ⋮ Hereditary classes of graphs: a parametric approach
Cites Work
- Unnamed Item
- The complexity ecology of parameters: An illustration using bounded max leaf number
- Graph minors. I. Excluding a forest
- The complexity of first-order and monadic second-order logic revisited
- Linear time solvable optimization problems on graphs of bounded clique-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Integer Programming with a Fixed Number of Variables
- Intractability of Clique-Width Parameterizations
- Deciding first-order properties of locally tree-decomposable structures
- The Traveling Salesman Problem with Many Visits to Few Cities
- Spanning Trees with Many Leaves
- Easy problems for tree-decomposable graphs
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Linear FPT reductions and computational lower bounds
- Graph Layout Problems Parameterized by Vertex Cover
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- (Meta) Kernelization
- Directed Nowhere Dense Classes of Graphs
- The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
- Improved Parameterized Upper Bounds for Vertex Cover
This page was built for publication: Algorithmic meta-theorems for restrictions of treewidth
