Algorithmic meta-theorems for restrictions of treewidth
From MaRDI portal
Publication:1759681
DOI10.1007/s00453-011-9554-xzbMath1252.68154MaRDI 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
68Q25: Analysis of algorithms and problem complexity
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
03B25: Decidability of theories and sets of sentences
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Unnamed Item, A Practical Algorithm for the Uniform Membership Problem of Labeled Multidigraphs of Tree-Width 2 for Spanning Tree Automata, How Bad is the Freedom to Flood-It?, Scattered Classes of Graphs, Unnamed Item, Unnamed Item, Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs, Parameterized (Approximate) Defective Coloring, Parameterized Complexity of Safe Set, Finer Tight Bounds for Coloring on Clique-Width, Letter graphs and geometric grid classes of permutations: characterization and recognition, Independent set reconfiguration parameterized by modular-width, Subgraph isomorphism on graph classes that exclude a substructure, Hull number: \(P_5\)-free graphs and reduction rules, Between treewidth and clique-width, Preprocessing subgraph and minor problems: when does a small vertex cover help?, Complexity of finding maximum regular induced subgraphs with prescribed degree, Practical algorithms for MSO model-checking on tree-decomposable graphs, Meta-kernelization with structural parameters, Simplified algorithmic metatheorems beyond MSO: treewidth and neighborhood diversity, 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, On the (parameterized) complexity of recognizing well-covered (\(r\),\(\ell\))-graph, Parameterized complexity of fair deletion problems, Parameterized complexity of happy coloring problems, Combinatorial \(n\)-fold integer programming and applications, The average cut-rank of graphs, Partitioning graphs into induced subgraphs, Width, depth, and space: tradeoffs between branching and dynamic programming, The graph motif problem parameterized by the structure of the input graph, Complexity and approximability of parameterized MAX-CSPs, Parameterized complexity of distance labeling and uniform channel assignment problems, Parameterized complexity of fair feedback vertex set problem, Fixed Parameter Complexity of Distance Constrained Labeling and Uniform Channel Assignment Problems, Evangelism in Social Networks, Between Treewidth and Clique-Width, Deterministic Algorithms for the Independent Feedback Vertex Set Problem, On the (Parameterized) Complexity of Recognizing Well-Covered $$(r,\ell )$$ -graphs, Unnamed Item, Unnamed Item
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
