Parameterizing by the number of numbers

DOI10.1007/s00224-011-9367-yzbMath1253.68173arXiv1007.2021OpenAlexW2125578939WikidataQ57359637 ScholiaQ57359637MaRDI QIDQ692894

Serge Gaspers, Michael R. Fellows, Frances A. Rosamond

Publication date: 6 December 2012

Published in: Theory of Computing Systems, Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.2021

zbMATH Keywords

parameterized complexitynumerical problemsproblem parameterizationvariety of a multiset

Mathematics Subject Classification ID

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

Related Items

Polynomial kernels for weighted problems ⋮ The complexity of probabilistic lobbying ⋮ On data reduction for dynamic vector bin packing ⋮ Knapsack problems: a parameterized point of view ⋮ Interval scheduling and colorful independent sets ⋮ Scheduling and fixed-parameter tractability ⋮ Combinatorial \(n\)-fold integer programming and applications ⋮ Approximating the multi-level bottleneck assignment problem ⋮ Complexity of splits reconstruction for low-degree trees ⋮ Parameterizing by the number of numbers ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ On explaining integer vectors by few homogeneous segments ⋮ Parameterized complexity of min-power asymmetric connectivity ⋮ Complexity of Splits Reconstruction for Low-Degree Trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Parameterizing by the number of numbers
• The complexity ecology of parameters: An illustration using bounded max leaf number
• On the parameterized complexity of multiple-interval graph problems
• Fixed-parameter algorithms for Kemeny rankings
• An application of simultaneous diophantine approximation in combinatorial optimization
• Approximation schemes for scheduling on parallel machines
• Fixed-parameter algorithms for CLOSEST STRING and related problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parametrized complexity theory.
• Integer Programming with a Fixed Number of Variables
• Complexity of Splits Reconstruction for Low-Degree Trees
• Reflections on Multivariate Algorithmics and Problem Parameterization
• Algorithms for Temperature-Aware Task Scheduling in Microprocessor Systems
• Algebraic Cryptanalysis
• Graph Layout Problems Parameterized by Vertex Cover
• Parameterized Complexity of Coloring Problems: Treewidth versus Vertex Cover
• Deconstructing Intractability: A Case Study for Interval Constrained Coloring
• Minkowski's Convex Body Theorem and Integer Programming
• Sorting and Searching in Multisets
• On Context-Free Languages