Parameterized complexity of asynchronous border minimization

DOI10.1007/s00453-018-0442-5zbMath1410.68165arXiv1503.08078OpenAlexW2804587996WikidataQ129735541 ScholiaQ129735541MaRDI QIDQ1755787

Martin Kronegger, Robert Ganian, Alexandru Popa, Andreas Pfandler

Publication date: 11 January 2019

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

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

zbMATH Keywords

NP-hard problemfixed-parameter tractabilityparameterized complexitymicroarrays

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Biochemistry, molecular biology (92C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (1)

Parameterized complexity of asynchronous border minimization

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Fast balanced partitioning is hard even on grids and trees
• Balanced graph partitioning
• An application of simultaneous diophantine approximation in combinatorial optimization
• Parameterized complexity of asynchronous border minimization
• Describing parameterized complexity classes
• Parametrized complexity theory.
• Hardness and Approximation of the Asynchronous Border Minimization Problem
• Integer Programming with a Fixed Number of Variables
• ON THE HARDNESS OF THE BORDER LENGTH MINIMIZATION PROBLEM ON A RECTANGULAR ARRAY
• Approximating Border Length for DNA Microarray Synthesis
• Graph Layout Problems Parameterized by Vertex Cover
• Minkowski's Convex Body Theorem and Integer Programming

This page was built for publication: Parameterized complexity of asynchronous border minimization