Back to Search
Start Over
Milling a Graph with Turn Costs: A Parameterized Complexity Perspective.
- Source :
- Graph Theoretic Concepts in Computer Science; 2010, p123-134, 12p
- Publication Year :
- 2010
-
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<subscript>x</subscript> 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISBNs :
- 9783642169250
- Database :
- Complementary Index
- Journal :
- Graph Theoretic Concepts in Computer Science
- Publication Type :
- Book
- Accession number :
- 76854431
- Full Text :
- https://doi.org/10.1007/978-3-642-16926-7_13