Milling a graph with turn costs: a parameterized complexity perspective

DOI10.1007/978-3-642-16926-7_13MaRDI QIDQ3057619zbMATH OpenOpenAlexWikidataFDO

Authors Michael R. Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Frances Rosamond, Nathan Yu, Sue Whitesides

Publication date 16 November 2010

Published in Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-16926-7_13

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Distance in graphs (05C12)

Recommendations

• Optimal Covering Tours with Turn Costs
• Optimal covering tours with turn costs
• Experimental evaluation of algorithms for the orthogonal milling problem with turn costs
• APPROXIMATION ALGORITHM FOR MULTIPLE-TOOL MILLING
• Approximation algorithms for lawn mowing and milling

Cites work

• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithms – ESA 2005
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• On the computational geometry of pocket machining
• Optimal Covering Tours with Turn Costs

Cited in

(11)

• Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs
• 1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids
• Experimental evaluation of algorithms for the orthogonal milling problem with turn costs
• What goes around comes around: covering tours and cycle covers with turn costs
• Parameterized analysis and crossing minimization problems
• On the complexity of some colorful problems parameterized by treewidth
• The Hamiltonian path graph is connected for simple s,t paths in rectangular grid graphs
• Minimum scan cover with angular transition costs
• Drawn tree decomposition: new approach for graph drawing problems
• 1-Complex $s,t$ Hamiltonian Paths: Structure and Reconfiguration in Rectangular Grids
• The Hamiltonian path graph is connected for simple \(s, t\) paths in rectangular grid graphs

This page was built for publication: Milling a graph with turn costs: a parameterized complexity perspective

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