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

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

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

(22)

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

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)