scientific article; zbMATH DE number 5790346

MaRDI QIDQ4929402zbMATH OpenFDO

Authors Apichat Heednacram, Francis Suraweera, Vladimir Estivill-Castro

Publication date 22 September 2010

Full work available at URL http://www.jucs.org/jucs_16_5/np_completeness_and_ftp

zbMATH Keywords

computational geometryparameterized complexityrestricted orientations

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Complexities of efficient solutions of rectilinear polygon cover problems
• Computational Science and Its Applications – ICCSA 2004
• The computational complexity and approximability of a series of geometric covering problems
• NP-completeness of some problems of partitioning and covering in graphs
• On rectangular covering problems
• scientific article; zbMATH DE number 4117851
• Further NP-hard problems for minimal polygon coverings
• On the computational complexity of optimization convex covering problems of graphs
• A linear-time heuristic for minimum rectangular coverings (Extended abstract)
• Algorithms for Rectangular Covering Problems

Cited in

(3)

• Covering paths for planar point sets
• Improved parameterized algorithms for minimum link-length rectilinear spanning path problem
• On covering points with minimum turns

This page was built for publication:

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