Train marshalling is fixed parameter tractable

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

doi:10.1007/978-3-642-30347-0_8

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 proceeding › Conference 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 language	English (US)
Title of host publication	Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings
Pages	51-56
Number of pages	6
DOIs	https://doi.org/10.1007/978-3-642-30347-0_8
State	Published - 2012
Externally published	Yes
Event	6th International Conference on Fun with Algorithms, FUN 2012 - Venice, Italy Duration: Jun 4 2012 → Jun 6 2012

Publication series

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

Other

Other	6th International Conference on Fun with Algorithms, FUN 2012
Country/Territory	Italy
City	Venice
Period	6/4/12 → 6/6/12

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-642-30347-0_8

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 Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings (pp. 51-56). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7288 LNCS). https://doi.org/10.1007/978-3-642-30347-0_8

@inproceedings{4769ee89fad64c9cbf645d2f3c43a9dd,

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.",

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",

doi = "10.1007/978-3-642-30347-0_8",

language = "English (US)",

isbn = "9783642303463",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "51--56",

booktitle = "Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings",

}

Brueggeman, L, Fellows, M, Fleischer, R, Lackner, M, Komusiewicz, C, Koutis, Y, Pfandler, A & Rosamond, F 2012, Train marshalling is fixed parameter tractable. in Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 7288 LNCS, pp. 51-56, 6th International Conference on Fun with Algorithms, FUN 2012, Venice, Italy, 6/4/12. https://doi.org/10.1007/978-3-642-30347-0_8

Train marshalling is fixed parameter tractable. / Brueggeman, Leo; Fellows, Michael; Fleischer, Rudolf et al.
Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings. 2012. p. 51-56 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7288 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

UR - http://www.scopus.com/inward/record.url?scp=84861994809&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84861994809&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-30347-0_8

DO - 10.1007/978-3-642-30347-0_8

M3 - Conference contribution

AN - SCOPUS:84861994809

SN - 9783642303463

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 51

EP - 56

BT - Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings

T2 - 6th International Conference on Fun with Algorithms, FUN 2012

Y2 - 4 June 2012 through 6 June 2012

ER -

Brueggeman L, Fellows M, Fleischer R, Lackner M, Komusiewicz C, Koutis Y et al. Train marshalling is fixed parameter tractable. In Fun with Algorithms - 6th International Conference, FUN 2012, Proceedings. 2012. p. 51-56. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-30347-0_8

Train marshalling is fixed parameter tractable

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this