Milling a graph with turn costs: a parameterized complexity perspective

Title: Milling a graph with turn costs: a parameterized complexity perspective
Creator: Fellows, Mike; Giannopoulos, Panos; Knauer, Christian; Paul, Christophe; Rosamond, Frances; Whitesides, Sue; Yu, Nathan
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
Publisher: Springer
Resource Type: conference paper
Date: 2010
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.
Subject: milling; parameterized complexity; turn costs
Identifier: http://hdl.handle.net/1959.13/933875
Identifier: uon:11740
Identifier: ISBN:9783642169250
Language: eng
Reviewed

		Thumbnail	File	Description	Size	Format