Train marshalling is fixed parameter tractable

Leo Brueggeman, Michael Fellows, Rudolf Fleischer, Martin Lackner, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler, Frances Rosamond

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

The train marshalling problem is about reordering the cars of a train using as few auxiliary rails as possible. The problem is known to be NP-complete. We show that it is fixed parameter tractable (FPT) with the number of auxiliary rails as parameter.

Original languageEnglish (US)
Title of host publicationFun with Algorithms - 6th International Conference, FUN 2012, Proceedings
Pages51-56
Number of pages6
DOIs
StatePublished - 2012
Externally publishedYes
Event6th International Conference on Fun with Algorithms, FUN 2012 - Venice, Italy
Duration: Jun 4 2012Jun 6 2012

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7288 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other6th International Conference on Fun with Algorithms, FUN 2012
CountryItaly
CityVenice
Period6/4/126/6/12

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Train marshalling is fixed parameter tractable'. Together they form a unique fingerprint.

Cite this