Milling a graph with turn costs: a parameterized complexity perspective | NOVA. The University of Newcastle's Digital Repository

Home

Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/933875

Title: Milling a graph with turn costs: a parameterized complexity perspective
Author/Creator: Fellows, Mike; Giannopoulos, Panos; Knauer, Christian; Paul, Christophe; Rosamond, Frances; Whitesides, Sue; Yu, Nathan
Institution: The University of Newcastle. Research Division, Office of the Deputy Vice-Chancellor (Research)
Description: 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.
Relation: 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: http://dx.doi.org/10.1007/978-3-642-16926-7_13
Date: 2010
Publisher: Springer
Keyword(s): milling; parameterized complexity; turn costs
Resource Type: conference paper
Identifier: http://hdl.handle.net/1959.13/933875
Identifier: ISBN:9783642169250

2 Visitors

4 Hits

NOVA. The University of Newcastle's Digital Repository