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.
Type de document :
Communication dans un congrès
WG'10: International Workshop on Graph Theoretic Concepts in Computer Science, Jun 2010, Zarós, Greece. pp.12, 2010, LNCS. 〈http://wg2010.thilikos.info/〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00533521
Contributeur : Christophe Paul <>
Soumis le : dimanche 7 novembre 2010 - 08:36:04
Dernière modification le : vendredi 1 juin 2018 - 15:24:01

Identifiants

  • 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, 2010, LNCS. 〈http://wg2010.thilikos.info/〉. 〈lirmm-00533521〉

Partager

Métriques

Consultations de la notice

109