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 Paper published in Proceedingspeer-review

    13 Downloads (Pure)


    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
    Title of host publicationFun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings
    EditorsEvangelos Kranakis, Danny Krizanc, Flaminia Luccio
    Place of PublicationOnline
    Number of pages6
    ISBN (Print)978-3-642-30346-3
    Publication statusPublished - 2012
    EventInternational Conference on Fun With Algorithms (FUN 2012 6th) - Venice, Italy, Venice, Italy
    Duration: 4 Jun 20126 Jun 2012
    Conference number: 2012 (6th)


    ConferenceInternational Conference on Fun With Algorithms (FUN 2012 6th)
    Abbreviated titleFUN

    Fingerprint Dive into the research topics of 'Train Marshalling Is Fixed Parameter Tractable'. Together they form a unique fingerprint.

    Cite this