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 Proceedings

    13 Downloads (Pure)

    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
    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
    PublisherSpringer
    Pages51-56
    Number of pages6
    Volume7288
    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)

    Conference

    ConferenceInternational Conference on Fun With Algorithms (FUN 2012 6th)
    Abbreviated titleFUN
    CountryItaly
    CityVenice
    Period4/06/126/06/12

      Fingerprint

    Cite this

    Brueggeman, L., Fellows, M., Fleischer, R., Lackner, M., Komusiewicz, C., Koutis, Y., Pfandler, A., & Rosamond, F. (2012). Train Marshalling Is Fixed Parameter Tractable. In E. Kranakis, D. Krizanc, & F. Luccio (Eds.), Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings (Vol. 7288, pp. 51-56). Springer.