Skip to Main content Skip to Navigation
Conference papers

Milling a Graph with Turn Costs: a Parameterized Complexity Perspective

Abstract : The Discrete Milling problem is a natural and quite gen- eral 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 fx 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.
Document type :
Conference papers
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533521
Contributor : Christophe Paul <>
Submitted on : Sunday, November 7, 2010 - 8:36:04 AM
Last modification on : Wednesday, August 28, 2019 - 1:34:00 PM

Identifiers

  • HAL Id : lirmm-00533521, version 1

Collections

Citation

Micheal Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Fran Rosamond, et al.. Milling a Graph with Turn Costs: a Parameterized Complexity Perspective. WG'10: International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.12. ⟨lirmm-00533521⟩

Share

Metrics

Record views

197