Milling a Graph with Turn Costs: A Parameterized Complexity Perspective

DOI10.1007/978-3-642-16926-7_13zbMath1309.68093OpenAlexW1961736623WikidataQ57359743 ScholiaQ57359743MaRDI QIDQ3057619

Panos Giannopoulos, Michael R. Fellows, Frances A. Rosamond, Christophe Paul, Nathan Yu, Christian Knauer, S. H. 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

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

Related Items (7)

1-complex \(s\), \(t\) Hamiltonian paths: structure and reconfiguration in rectangular grids ⋮ Parameterized analysis and crossing minimization 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 ⋮ On the complexity of some colorful problems parameterized by treewidth ⋮ Minimum Scan Cover with Angular Transition Costs ⋮ Reconfiguring simple \(s\), \(t\) Hamiltonian paths in rectangular grid graphs

Cites Work

• Unnamed Item
• On the computational geometry of pocket machining
• On the Complexity of Some Colorful Problems Parameterized by Treewidth
• Optimal Covering Tours with Turn Costs
• Algorithms – ESA 2005

This page was built for publication: Milling a Graph with Turn Costs: A Parameterized Complexity Perspective