A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

Bodlaender, Hans L.; Fomin, Fedor; Koster, Arie M.C.A.; Kratsch, Dieter; Thilikos, Dimitrios M.
Peer reviewed, Journal article
Published version
Thumbnail
Åpne
Permanent lenke
https://hdl.handle.net/1956/4556
Utgivelsesdato
2011-01-21
Metadata
Vis full innførsel
Samlinger
Originalversjon
https://doi.org/10.1007/s00224-011-9312-0
Sammendrag
In this note, we give a proof that several vertex ordering problems can be solved in O ∗(2 n ) time and O ∗(2 n ) space, or in O ∗(4 n ) time and polynomial space. The algorithms generalize algorithms for the Travelling Salesman Problem by Held and Karp (J. Soc. Ind. Appl. Math. 10:196–210, 1962) and Gurevich and Shelah (SIAM J. Comput. 16:486–502, 1987). We survey a number of vertex ordering problems to which the results apply.
Utgiver
Springer
Opphavsrett
The Author(s) 2011
Copyright The Author(s) 2011. This article is published with open access at Springerlink.com
Attribution-NonCommercial CC BY-NC
Med mindre annet er angitt, så er denne innførselen lisensiert som Attribution-NonCommercial CC BY-NC