Aspects of a multivariate complexity analysis for rectangle tiling

DOI10.1016/J.ORL.2011.06.001MaRDI QIDQ408398zbMATH OpenOpenAlexFDO

Authors André Nichterlein, Michael Dom, Rolf Niedermeier

Publication date 5 April 2012

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2011.06.001

zbMATH Keywords

computational complexityfixed-parameter tractabilityNP-hardnesscombinatorial algorithms

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A New Approximation Algorithm for Multidimensional Rectangle Tiling
• Tile complexity of approximate squares
• The complexity of generalized domino tilings
• The Tiling Problem Revisited (Extended Abstract)
• Tile Complexity of Linear Assemblies
• The Tile Complexity of Linear Assemblies
• Efficient approximation algorithms for tiling and packing problems with rectangles
• Rectangular Tiling in Multidimensional Arrays
• Complexity of tiling a polygon with trominoes or bars
• Deciding multiple tiling by polygons in polynomial time

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1303579 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Automata, Languages and Programming
• Compressed histograms with arbitrary bucket layouts for selectivity estimation
• Deconstructing intractability-A multivariate complexity analysis of interval constrained coloring
• Efficient approximation algorithms for tiling and packing problems with rectangles
• New approximation algorithm for RTILE problem.
• Parameterized and Exact Computation
• Parametrized complexity theory.
• Rectangular Tiling in Multidimensional Arrays
• Reflections on multivariate algorithmics and problem parameterization
• Towards fully multivariate algorithmics: some new results and directions in parameter ecology

Cited in

(3)

• Tile complexity of approximate squares
• Tile Complexity of Linear Assemblies
• A multiparameter analysis of domino tiling with an application to concurrent systems

This page was built for publication: Aspects of a multivariate complexity analysis for rectangle tiling

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