Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Milling a Graph with Turn Costs: A Parameterized Complexity Perspective

Fellows, Michael, Giannopoulos, Panos, Knauer, Christian, Paul, Christophe, Rosamond, Frances, Whitesides, Sue and Yu, Nathan (2010). Milling a Graph with Turn Costs: A Parameterized Complexity Perspective. In: Thilikos, Dimitrios M. WG 2010. 36th International Workshop on Graph-Theoretic Concepts in Computer Science, Zaros, Crete, Greece, 28-30 June 2010.

Document type: Conference Paper

IRMA ID 83093774xPUB56
Author Fellows, Michael
Giannopoulos, Panos
Knauer, Christian
Paul, Christophe
Rosamond, Frances
Whitesides, Sue
Yu, Nathan
Title Milling a Graph with Turn Costs: A Parameterized Complexity Perspective
Conference Name WG 2010. 36th International Workshop on Graph-Theoretic Concepts in Computer Science
Conference Location Zaros, Crete, Greece
Conference Dates 28-30 June 2010
Conference Publication Title Lecture Notes in Computer Science Series
Editor Thilikos, Dimitrios M.
Place of Publication Germany
Publisher Springer
Publication Year 2010
Volume Number 6410
ISBN 978-3-642-16925-0   (check CDU catalogue  open catalogue search in new window)
ISSN 0302-9743   (check CDU catalogue  open catalogue search in new window)
Start Page 123
End Page 134
Total Pages 12
HERDC Category E1 - Conference Publication (DIISR)
Abstract 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.
Additional Notes http://link.springer.com/chapter/10.1007/978-3-642-16926-7_13
 
Versions
Version Filter Type
Access Statistics: 18 Abstract Views  -  Detailed Statistics
Created: Fri, 17 Jan 2014, 00:13:49 CST