2009/12/05 by M. Fellows, Michael R. Fellows, Fellows, M. +18
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #cs.CC #cs.CG #cs.DS #cs.LO
paper · pdf · doi:10.48550/arxiv.0912.1050
18 pages, 2 figures
arxiv created 2009/12/05 · arxiv updated 2009/12/08
The Abstract Milling problem is a natural and quite general graph-theoretic model for geometric milling problems. Given a graph, one asks for a walk that covers all its vertices with a minimum number of turns, as specified in the graph model by a 0/1 turncost function fx at each vertex x giving, for each ordered pair of edges (e,f) incident at x, the turn cost at x of a walk that enters the vertex on edge e and departs on edge f. We describe an initial study of the parameterized complexity of the problem. Our main positive result shows that Abstract Milling, parameterized by: number of turns, treewidth and maximum degree, is fixed-parameter tractable, We also show that Abstract Milling parameterized by (only) the number of turns and the pathwidth, is hard for W[1] -- one of the few parameterized intractability results for bounded pathwidth.