Milling a Graph with Turn Costs: a Parameterized Complexity Perspective - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
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.
Fichier principal
Vignette du fichier
ark__67375_HCB-Z2TRBNN3-Z.pdf (462.55 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

lirmm-00533521 , version 1 (08-03-2024)

Identifiers

Cite

Micheal Fellows, Panos Giannopoulos, Christian Knauer, Christophe Paul, Fran Rosamond, et al.. Milling a Graph with Turn Costs: a Parameterized Complexity Perspective. WG 2010 - 36th International Workshop on Graph-Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.123-134, ⟨10.1007/978-3-642-16926-7_13⟩. ⟨lirmm-00533521⟩
316 View
16 Download

Altmetric

Share

More