New Races in Parameterized Algorithmics

DOI10.1007/978-3-642-32589-2_2zbMath1365.68286OpenAlexW127421644MaRDI QIDQ2912706

Rolf Niedermeier, Christian Komusiewicz

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)

Related Items (24)

Win-win kernelization for degree sequence completion problems ⋮ Finding disjoint paths on edge-colored graphs: more tractability results ⋮ Parameterized complexity and approximation issues for the colorful components problems ⋮ \(\mathrm{H}\)-index manipulation by merging articles: models, theory, and experiments ⋮ Prices matter for the parameterized complexity of shift bribery ⋮ 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 ⋮ Refining the complexity of the sports elimination problem ⋮ Further hardness results on rainbow and strong rainbow connectivity ⋮ A more fine‐grained complexity analysis of finding the most vital edges for undirected shortest paths ⋮ Multivariate algorithmics for finding cohesive subnetworks ⋮ Complexity of rainbow vertex connectivity problems for restricted graph classes ⋮ Fixed-parameter algorithms for DAG partitioning ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ Constant thresholds can make target set selection tractable ⋮ On explaining integer vectors by few homogeneous segments ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review ⋮ The Power of Linear-Time Data Reduction for Maximum Matching ⋮ On structural parameterizations for the 2-club problem ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ A refined complexity analysis of degree anonymization in graphs ⋮ Myhill-Nerode Methods for Hypergraphs

This page was built for publication: New Races in Parameterized Algorithmics