Train Marshalling Is Fixed Parameter Tractable

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

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 Paper published in Proceedings › peer-review

9 Citations (Scopus)

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 language	English
Title of host publication	Fun with Algorithms 6th International Conference FUN 2012 Venice Italy June 4-6 2012 Proceedings
Editors	Evangelos Kranakis, Danny Krizanc, Flaminia Luccio
Place of Publication	Online
Publisher	Springer
Pages	51-56
Number of pages	6
Volume	7288
ISBN (Print)	978-3-642-30346-3
Publication status	Published - 2012
Event	International Conference on Fun With Algorithms (FUN 2012 6th) - Venice, Italy, Venice, Italy Duration: 4 Jun 2012 → 6 Jun 2012 Conference number: 2012 (6th)

Conference

Conference	International Conference on Fun With Algorithms (FUN 2012 6th)
Abbreviated title	FUN
Country/Territory	Italy
City	Venice
Period	4/06/12 → 6/06/12

Cite this

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

note = "International Conference on Fun With Algorithms (FUN 2012 6th), FUN ; Conference date: 04-06-2012 Through 06-06-2012",

}

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 et al.
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 proceeding › Conference Paper published in Proceedings › peer-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

N1 - Conference code: 2012 (6th)

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

T2 - International Conference on Fun With Algorithms (FUN 2012 6th)

Y2 - 4 June 2012 through 6 June 2012

ER -

Train Marshalling Is Fixed Parameter Tractable

Abstract

Conference

Other files and links

Fingerprint

Cite this