Ubiquitous parameterization -- invitation to fixed-parameter algorithms

DOI10.1007/978-3-540-28629-5_4MaRDI QIDQ5311126zbMATH OpenOpenAlexFDO

Authors Rolf Niedermeier

Publication date 22 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b99679

zbMATH Keywords

fixed-parameter algorithmsNP-hardnessparameterizationparameterized complexity

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2234775
• Algorithms and Data Structures
• scientific article; zbMATH DE number 806748
• Parameterized complexity: the main ideas and connections to practical computing
• Parameterized complexity: The main ideas and connections to practical computing

Cited in

(24)

• A fixed-parameter tractability result for multicommodity demand flow in trees
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Combinatorial \(n\)-fold integer programming and applications
• Domino sequencing: scheduling with state-based sequence-dependent setup times
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Integer programming in parameterized complexity: five miniatures
• Fixed-parameter tractability, a prehistory
• A basic parameterized complexity primer
• New races in parameterized algorithmics
• Reflections on multivariate algorithmics and problem parameterization
• Fixed-parameter tractability and data reduction for multicut in trees
• Parameterized complexity: The main ideas and connections to practical computing
• Confronting intractability via parameters
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Integer programming in parameterized complexity: three miniatures
• Parameterized Algorithms
• Combinatorial \(n\)-fold integer programming and applications
• A structural view on parameterizing problems: Distance from triviality
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• The parameterized complexity of guarding almost convex polygons
• Approximate Turing kernelization for problems parameterized by treewidth
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Exact algorithms and applications for tree-like Weighted Set Cover

This page was built for publication: Ubiquitous parameterization -- invitation to fixed-parameter algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5311126)