Train Marshalling Is Fixed Parameter Tractable | SpringerLink
Skip to main content
Springer Nature Link
Log in

Train Marshalling Is Fixed Parameter Tractable

  • Conference paper
Fun with Algorithms (FUN 2012)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 7288))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Acta Mathematicae Applicatae Sinica 1(2), 91–105 (1978)

    Google Scholar 

  2. Dalhaus, E., Horak, P., Miller, M., Ryan, J.F.: Algorithms for combinatorial problems related to train marshalling. CiteSeerX (10.1.1.37.4090) (2000), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.4090

  3. Dalhaus, E., Horak, P., Miller, M., Ryan, J.F.: The train marshalling problem. Discrete Applied Mathematics 103(1-3), 41–54 (2000)

    Article  MathSciNet  Google Scholar 

  4. Zhu, Y., Zhu, R.: Sequence reconstruction under some order-type constraints. Scientia Sinica 26(7), 702–713 (1983)

    MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of California, Santa Cruz, USA

    Leo Brueggeman

  2. Charles Darwin University, Darwin, Australia

    Michael Fellows & Frances Rosamond

  3. SCS and IIPL, Fudan University, Shanghai, China

    Rudolf Fleischer

  4. GUtech, Muscat, Oman

    Rudolf Fleischer

  5. Vienna University of Technology, Austria

    Martin Lackner & Andreas Pfandler

  6. TU Berlin, Germany

    Christian Komusiewicz

  7. University of Puerto Rico, Puerto Rico

    Yiannis Koutis

Authors
  1. Leo Brueggeman
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael Fellows
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rudolf Fleischer
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Martin Lackner
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Christian Komusiewicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yiannis Koutis
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Andreas Pfandler
    View author publications

    You can also search for this author in PubMed Google Scholar

  8. Frances Rosamond
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computer Science, Carleton University, 1125 Col. By Dr., K1S 5B6, Ottawa, ON, Canada

    Evangelos Kranakis

  2. Department of Mathematics and Computer Science, Wesleyan University, 06459, Middleton, CT, USA

    Danny Krizanc

  3. Dipartimento di Scienze Ambientali, Informatica e Statistica, Università Ca’ Foscari, Via Torino 155, 30172, Mestre (Ve), Italy

    Flaminia Luccio

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Brueggeman, L. et al. (2012). Train Marshalling Is Fixed Parameter Tractable. In: Kranakis, E., Krizanc, D., Luccio, F. (eds) Fun with Algorithms. FUN 2012. Lecture Notes in Computer Science, vol 7288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30347-0_8

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-30347-0_8

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-30346-3

  • Online ISBN: 978-3-642-30347-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation