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 ProceedingsResearchpeer-review

    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

    Rails
    Railroad cars

    Cite this

    Brueggeman, L., Fellows, M., Fleischer, R., Lackner, M., Komusiewicz, C., Koutis, Y., ... 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). Online: Springer.
    Brueggeman, Leo ; Fellows, Michael ; Fleischer, Rudolf ; Lackner, Martin ; Komusiewicz, Christian ; Koutis, Yiannis ; Pfandler, Andreas ; Rosamond, Frances. / Train Marshalling Is Fixed Parameter Tractable. Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings. editor / Evangelos Kranakis ; Danny Krizanc ; Flaminia Luccio. Vol. 7288 Online : Springer, 2012. pp. 51-56
    @inproceedings{c5a743dbfc2e4701b559c05d49b93406,
    title = "Train Marshalling Is Fixed Parameter Tractable",
    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.",
    keywords = "A-train, Fixed parameters, NP Complete, Artificial intelligence, Algorithms",
    author = "Leo Brueggeman and Michael Fellows and Rudolf Fleischer and Martin Lackner and Christian Komusiewicz and Yiannis Koutis and Andreas Pfandler and Frances Rosamond",
    year = "2012",
    language = "English",
    isbn = "978-3-642-30346-3",
    volume = "7288",
    pages = "51--56",
    editor = "Evangelos Kranakis and Danny Krizanc and Flaminia Luccio",
    booktitle = "Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings",
    publisher = "Springer",
    address = "Switzerland",

    }

    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, Springer, Online, pp. 51-56, International Conference on Fun With Algorithms (FUN 2012 6th), Venice, Italy, 4/06/12.

    Train Marshalling Is Fixed Parameter Tractable. / Brueggeman, Leo; Fellows, Michael; Fleischer, Rudolf; Lackner, Martin; Komusiewicz, Christian; Koutis, Yiannis; Pfandler, Andreas; Rosamond, Frances.

    Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings. ed. / Evangelos Kranakis; Danny Krizanc; Flaminia Luccio. Vol. 7288 Online : Springer, 2012. p. 51-56.

    Research output: Chapter in Book/Report/Conference proceedingConference Paper published in ProceedingsResearchpeer-review

    TY - GEN

    T1 - Train Marshalling Is Fixed Parameter Tractable

    AU - Brueggeman, Leo

    AU - Fellows, Michael

    AU - Fleischer, Rudolf

    AU - Lackner, Martin

    AU - Komusiewicz, Christian

    AU - Koutis, Yiannis

    AU - Pfandler, Andreas

    AU - Rosamond, Frances

    PY - 2012

    Y1 - 2012

    N2 - 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.

    AB - 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.

    KW - A-train

    KW - Fixed parameters

    KW - NP Complete

    KW - Artificial intelligence

    KW - Algorithms

    UR - http://www.dsi.unive.it/~fun2012/

    M3 - Conference Paper published in Proceedings

    SN - 978-3-642-30346-3

    VL - 7288

    SP - 51

    EP - 56

    BT - Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings

    A2 - Kranakis, Evangelos

    A2 - Krizanc, Danny

    A2 - Luccio, Flaminia

    PB - Springer

    CY - Online

    ER -

    Brueggeman L, Fellows M, Fleischer R, Lackner M, Komusiewicz C, Koutis Y et al. Train Marshalling Is Fixed Parameter Tractable. In Kranakis E, Krizanc D, Luccio F, editors, Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings. Vol. 7288. Online: Springer. 2012. p. 51-56