The complexity ecology of parameters: An illustration using bounded max leaf number
From MaRDI portal
Publication:733736
DOI10.1007/S00224-009-9167-9zbMATH Open1184.05123DBLPjournals/mst/FellowsLMMRS09OpenAlexW1971818177WikidataQ29397585 ScholiaQ29397585MaRDI QIDQ733736FDOQ733736
Daniel Lokshtanov, Matthias Mnich, Saket Saurabh, Michael R. Fellows, Neeldhara Misra, Frances 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
Recommendations
- The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
- Circumscribed Complexity in Ecological Networks
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
- A complexity-based measure and its application to phylogenetic analysis
- On the generality of stability-complexity relationships in Lotka-Volterra ecosystems
- The [extended] maximum entropy formalism and the statistical structure of ecosystems
- Dynamic complexity of a host-parasitoid ecological model with the hassell growth function for the host
- A search for maximum species abundances in ecological communities under conditional diversity optimization
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)
Cites Work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Which problems have strongly exponential complexity?
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Spanning Trees with Many Leaves
- Easy problems for tree-decomposable graphs
- The Traveling-Salesman Problem and Minimum Spanning Trees
- Title not available (Why is that?)
- Vertex packings: Structural properties and algorithms
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Quickly excluding a forest
- Graph-Theoretic Concepts in Computer Science
- Fixed-parameter tractability and completeness II: On completeness for W[1]
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
- Polynomial-time data reduction for dominating set
- Graph Layout Problems Parameterized by Vertex Cover
- Improved Parameterized Upper Bounds for Vertex Cover
- Bidimensionality: new connections between FPT algorithms and PTASs
- Title not available (Why is that?)
- Graph-Theoretic Concepts in Computer Science
- Tight lower bounds for certain parameterized NP-hard problems
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the parameterized complexity of short computation and factorization
- A Cubic Kernel for Feedback Vertex Set
- Title not available (Why is that?)
- On the Complexity of Some Colorful Problems Parameterized by Treewidth
- Title not available (Why is that?)
- Algorithms and Data Structures
- Monadic Second Order Logic on Graphs with Local Cardinality Constraints
- An analysis of ML typability
- The complexity of type inference for higher-order typed lambda calculi
- Mathematical Foundations of Computer Science 2004
Cited In (28)
- Two-layer planarization parameterized by feedback edge set
- Kernel bounds for path and cycle problems
- On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem
- Data Reduction for Graph Coloring Problems
- Kernelization for feedback vertex set via elimination distance to a forest
- Sublinear approximation algorithms for boxicity and related problems
- Kernelization for feedback vertex set via elimination distance to a forest
- Kernel Bounds for Path and Cycle Problems
- Kernelization of Graph Hamiltonicity: Proper $H$-Graphs
- The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
- Polynomial kernels for vertex cover parameterized by small degree modulators
- Kernelization – Preprocessing with a Guarantee
- Algorithmic meta-theorems for restrictions of treewidth
- On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal
- Bounds and algorithms for geodetic hulls
- Data reduction for graph coloring problems
- The parameterized complexity of cycle packing: indifference is not an issue
- Bivariate Complexity Analysis of Almost Forest Deletion
- Monitoring edge-geodetic sets in graphs
- Parameterizing by the number of numbers
- Bivariate complexity analysis of \textsc{Almost Forest Deletion}
- The parameterized complexity of some minimum label problems
- Dominating complex networks by identifying minimum skeletons
- Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter
- A 2-approximation algorithm for finding a spanning tree with maximum number of leaves
- The graph motif problem parameterized by the structure of the input graph
- Robust Connectivity of Graphs on Surfaces
- Packing arc-disjoint cycles in oriented graphs
This page was built for publication: The complexity ecology of parameters: An illustration using bounded max leaf number
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q733736)
