Milling a Graph with Turn Costs: a Parameterized Complexity Perspective - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2010

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.
No file

Dates and versions

lirmm-00533521 , version 1 (07-11-2010)

Identifiers

  • HAL Id : lirmm-00533521 , version 1

Cite

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⟩
257 View
0 Download

Share

Gmail Facebook X LinkedIn More