Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/933875
- Milling a graph with turn costs: a parameterized complexity perspective
- The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
- The DISCRETE 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 f x 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.
- 36th International Workshop on Graph-Theoretic Concepts in Computer (WG 2010). Graph Theoretic Concepts in Computer Science: Revised Papers (Zarós, Greece 28-30 June, 2008) p. 123-134
- Publisher Link
- Resource Type
- conference paper