Algorithmic meta-theorems for restrictions of treewidth
From MaRDI portal
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Decidability of theories and sets of sentences (03B25)
Recommendations
- Algorithmic meta-theorems for restrictions of treewidth
- Algorithmic meta theorems for sparse graph classes
- Logic, graphs, and algorithms
- A gentle introduction to applications of algorithmic metatheorems for space and circuit classes
- Expanding the expressive power of monadic second-order logic on restricted graph classes
Cites work
- scientific article; zbMATH DE number 1254648 (Why is no real title available?)
- (Meta) Kernelization
- Deciding first-order properties of locally tree-decomposable structures
- Directed Nowhere Dense Classes of Graphs
- Easy problems for tree-decomposable graphs
- Graph Layout Problems Parameterized by Vertex Cover
- Graph minors. I. Excluding a forest
- Improved Parameterized Upper Bounds for Vertex Cover
- Integer Programming with a Fixed Number of Variables
- Intractability of clique-width parameterizations
- Linear FPT reductions and computational lower bounds
- Linear time solvable optimization problems on graphs of bounded clique-width
- Spanning Trees with Many Leaves
- The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
- The Traveling Salesman Problem with Many Visits to Few Cities
- The complexity ecology of parameters: An illustration using bounded max leaf number
- The complexity of first-order and monadic second-order logic revisited
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
Cited in
(94)- Target Set Selection in Dense Graph Classes
- Combinatorial \(n\)-fold integer programming and applications
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
- Practical algorithms for MSO model-checking on tree-decomposable graphs
- Parameterized complexity for iterated type partitions and modular-width
- How bad is the freedom to Flood-It?
- Expanding the expressive power of monadic second-order logic on restricted graph classes
- Parameterized algorithms for the happy set problem
- Complexity of finding maximum regular induced subgraphs with prescribed degree
- An algorithmic metatheorem for directed treewidth
- Parameterized complexity of locally minimal defensive alliances
- Rainbow independent sets on dense graph classes
- The balanced satisfactory partition problem
- The micro-world of cographs
- Letter graphs and geometric grid classes of permutations: characterization and recognition
- Grundy Distinguishes Treewidth from Pathwidth
- Vertex partitioning problems on graphs with bounded tree width
- Winner determination algorithms for graph games with matching structures
- Finer tight bounds for coloring on clique-width
- Finer tight bounds for coloring on clique-width
- The average cut-rank of graphs
- A Survey on the Complexity of Flood-Filling Games
- Computing densest \(k\)-subgraph with structural parameters
- Critical properties of bipartite permutation graphs
- Hereditary classes of graphs: a parametric approach
- How Bad is the Freedom to Flood-It?
- Algorithmic meta theorems for circuit classes of constant and logarithmic depth
- The parameterized complexity of terminal monitoring set
- Complexity and approximability of parameterized MAX-CSPs
- Spanning trees with few branch vertices in graphs of bounded neighborhood diversity
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Width, depth, and space: tradeoffs between branching and dynamic programming
- Winner determination algorithms for graph games with matching structures
- Can Romeo and Juliet meet? Or rendezvous games with adversaries on graphs
- Algorithms, kernels and lower bounds for the flood-it game parameterized by the vertex cover number
- On the computational complexity of the bipartizing matching problem
- Refined notions of parameterized enumeration kernels with applications to matching cut enumeration
- Hull number: \(P_5\)-free graphs and reduction rules
- Between treewidth and clique-width
- Getting linear time in graphs of bounded neighborhood diversity
- The small set vertex expansion problem
- Integer programming in parameterized complexity: three miniatures
- On supergraphs satisfying CMSO properties
- On structural parameterizations of star coloring
- Evangelism in social networks
- Twin-treewidth: a single-exponential logic-based approach
- Algorithmic meta-theorems for restrictions of treewidth
- Grouped domination parameterized by vertex cover, twin cover, and beyond
- Scattered classes of graphs
- Parameterized (approximate) defective coloring
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- A practical algorithm for the uniform membership problem of labeled multidigraphs of tree-width 2 for spanning tree automata
- Extended MSO model checking via small vertex integrity
- Digraph coloring and distance to acyclicity
- Parameterized (approximate) defective coloring
- On the harmless set problem parameterized by treewidth
- Parameterized complexity of immunization in the threshold model
- Immunization in the threshold model: a parameterized complexity study
- Structural parameterization of cluster deletion
- Algorithmic meta-theorems for combinatorial reconfiguration revisited
- Meta-kernelization with structural parameters
- Parameterized complexity of fair feedback vertex set problem
- Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems
- Parameterized complexity of satisfactory partition problem
- Dynamic coloring on restricted graph classes
- Serial and parallel kernelization of multiple hitting set parameterized by the Dilworth number, implemented on the GPU
- Grundy distinguishes treewidth from pathwidth
- Preprocessing subgraph and minor problems: when does a small vertex cover help?
- Parameterized Complexity of Fair Feedback Vertex Set Problem
- Integer programming in parameterized complexity: five miniatures
- A note on coloring \((4K_1, C_4, C_6)\)-free graphs with a \(C_7\)
- The structural complexity landscape of finding balance-fair shortest paths
- Courcelle's theorem for triangulations
- A 3/2-Approximation for the Metric Many-Visits Path TSP
- Parameterized complexity of safe set
- On Structural Parameterizations of the Harmless Set Problem
- Treewidth with a quantifier alternation revisited
- Parameterizing path partitions
- Subgraph isomorphism on graph classes that exclude a substructure
- Structural parameterizations of vertex integrity
- On the (parameterized) complexity of recognizing well-covered \((r,\ell)\)-graphs
- Parameterizing path partitions
- Parameterized complexity of happy coloring problems
- Parameterized complexity of fair vertex evaluation problems
- Algorithmic meta theorems for sparse graph classes
- scientific article; zbMATH DE number 7561372 (Why is no real title available?)
- On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph
- Between treewidth and clique-width
- The Micro-world of Cographs
- scientific article; zbMATH DE number 7029306 (Why is no real title available?)
- The graph motif problem parameterized by the structure of the input graph
- Parameterized complexity of distance labeling and uniform channel assignment problems
- Combinatorial \(n\)-fold integer programming and applications
This page was built for publication: Algorithmic meta-theorems for restrictions of treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759681)
