- 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
- Hits: 3304
- Visitors: 3268
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|