The complexity ecology of parameters: An illustration using bounded max leaf number
From MaRDI portal
Publication:733736
DOI10.1007/s00224-009-9167-9zbMath1184.05123OpenAlexW1971818177WikidataQ29397585 ScholiaQ29397585MaRDI QIDQ733736
Daniel Lokshtanov, Matthias Mnich, Saket Saurabh, Michael R. Fellows, Neeldhara Misra, Frances A. Rosamond
Publication date: 19 October 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s00224-009-9167-9
Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal, Kernel Bounds for Path and Cycle Problems, On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem, Kernelization – Preprocessing with a Guarantee, Bivariate Complexity Analysis of Almost Forest Deletion, The graph motif problem parameterized by the structure of the input graph, Robust Connectivity of Graphs on Surfaces, Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter, Two-layer planarization parameterized by feedback edge set, Kernel bounds for path and cycle problems, Data reduction for graph coloring problems, Kernelization for feedback vertex set via elimination distance to a forest, Bivariate complexity analysis of \textsc{Almost Forest Deletion}, Bounds and algorithms for geodetic hulls, Kernelization for feedback vertex set via elimination distance to a forest, Sublinear approximation algorithms for boxicity and related problems, Packing arc-disjoint cycles in oriented graphs, Monitoring edge-geodetic sets in graphs, Dominating complex networks by identifying minimum skeletons, The parameterized complexity of some minimum label problems, A 2-approximation algorithm for finding a spanning tree with maximum number of leaves, Parameterizing by the number of numbers, Algorithmic meta-theorems for restrictions of treewidth, The parameterized complexity of cycle packing: indifference is not an issue, Data Reduction for Graph Coloring Problems, Kernelization of Graph Hamiltonicity: Proper $H$-Graphs, Polynomial kernels for vertex cover parameterized by small degree modulators
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Graph minors. XX: Wagner's conjecture
- Quickly excluding a forest
- On the parameterized complexity of short computation and factorization
- Which problems have strongly exponential complexity?
- Tight lower bounds for certain parameterized NP-hard problems
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Spanning Trees with Many Leaves
- Easy problems for tree-decomposable graphs
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Polynomial-time data reduction for dominating set
- A Cubic Kernel for Feedback Vertex Set
- Graph Layout Problems Parameterized by Vertex Cover
- Monadic Second Order Logic on Graphs with Local Cardinality Constraints
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- Vertex packings: Structural properties and algorithms
- An analysis of ML typability
- The complexity of type inference for higher-order typed lambda calculi
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Mathematical Foundations of Computer Science 2004
- The Traveling-Salesman Problem and Minimum Spanning Trees
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph-Theoretic Concepts in Computer Science
- Graph-Theoretic Concepts in Computer Science
- Improved Parameterized Upper Bounds for Vertex Cover
- Algorithms and Data Structures
- Graph-Theoretic Concepts in Computer Science
