The complexity ecology of parameters: An illustration using bounded max leaf number

DOI10.1007/S00224-009-9167-9MaRDI QIDQ733736zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Saket Saurabh, 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

zbMATH Keywords

bandwidthparameterized complexitykernelizationmax-leafwell-quasiordering

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

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

Cites work

• scientific article; zbMATH DE number 2086260 (Why is no real title available?)
• scientific article; zbMATH DE number 3906520 (Why is no real title available?)
• scientific article; zbMATH DE number 3910446 (Why is no real title available?)
• scientific article; zbMATH DE number 1956210 (Why is no real title available?)
• scientific article; zbMATH DE number 2080462 (Why is no real title available?)
• scientific article; zbMATH DE number 1499087 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Cubic Kernel for Feedback Vertex Set
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Algorithms and Data Structures
• An analysis of ML typability
• Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
• Bidimensionality: new connections between FPT algorithms and PTASs
• Easy problems for tree-decomposable graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Graph Layout Problems Parameterized by Vertex Cover
• Graph minors. XX: Wagner's conjecture
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• Improved Parameterized Upper Bounds for Vertex Cover
• Mathematical Foundations of Computer Science 2004
• Monadic Second Order Logic on Graphs with Local Cardinality Constraints
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• On the parameterized complexity of short computation and factorization
• Polynomial-time data reduction for dominating set
• Quickly excluding a forest
• Spanning Trees with Many Leaves
• The Traveling-Salesman Problem and Minimum Spanning Trees
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• The complexity of type inference for higher-order typed lambda calculi
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Tight lower bounds for certain parameterized NP-hard problems
• Vertex packings: Structural properties and algorithms
• Which problems have strongly exponential complexity?

Cited in

(27)

• Two-layer planarization parameterized by feedback edge set
• Kernel bounds for path and cycle problems
• Packing arc-disjoint cycles in oriented graphs
• On polynomial kernels for structural parameterizations of odd cycle transversal
• 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
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Polynomial kernels for vertex cover parameterized by small degree modulators
• The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number
• Robust connectivity of graphs on surfaces
• Algorithmic meta-theorems for restrictions of treewidth
• Kernelization -- preprocessing with a guarantee
• Bounds and algorithms for geodetic hulls
• Data reduction for graph coloring problems
• Data reduction for graph coloring problems
• The parameterized complexity of cycle packing: indifference is not an issue
• Kernel bounds for path and cycle problems
• Monitoring edge-geodetic sets in graphs
• On the analysis of the \((1+1)\) evolutionary algorithm for the maximum leaf spanning tree problem
• Bivariate complexity analysis of \textsc{Almost Forest Deletion}
• Kernelization of graph Hamiltonicity: proper \(H\)-graphs
• 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

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)