New races in parameterized algorithmics

DOI10.1007/978-3-642-32589-2_2MaRDI QIDQ2912706zbMATH OpenOpenAlexFDO

Authors Christian Komusiewicz, Rolf Niedermeier

Publication date 25 September 2012

Published in Mathematical Foundations of Computer Science 2012 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-32589-2_2

Mathematics Subject Classification ID

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

Recommendations

• Faster exact algorithms for hard problems: A parameterized point of view
• scientific article; zbMATH DE number 2234775
• A general method to speed up fixed-parameter-tractable algorithms
• Parameterized complexity: the main ideas and connections to practical computing
• Mathematical Foundations of Computer Science 2004

Cited in

(21)

• Multivariate algorithmics for finding cohesive subnetworks
• scientific article; zbMATH DE number 5829047 (Why is no real title available?)
• Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• A refined complexity analysis of finding the most vital edges for undirected shortest paths
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• Constant thresholds can make target set selection tractable
• Further hardness results on rainbow and strong rainbow connectivity
• Parameterized complexity of machine scheduling: 15 open problems
• Win-win kernelization for degree sequence completion problems
• Prices matter for the parameterized complexity of shift bribery
• Algorithms and Data Structures
• \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments
• The Power of Linear-Time Data Reduction for Maximum Matching
• Refining the complexity of the sports elimination problem
• A refined complexity analysis of degree anonymization in graphs
• Complexity of rainbow vertex connectivity problems for restricted graph classes
• Fixed-parameter algorithms for DAG partitioning
• On explaining integer vectors by few homogeneous segments
• The graph motif problem parameterized by the structure of the input graph
• On making a distinguished vertex of minimum degree by vertex deletion

This page was built for publication: New races in parameterized algorithmics

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