A note on exact algorithms for vertex ordering problems on graphs

H.L. Bodlaender; F.V. Fomin; Arie M C A Koster; Dieter Kratsch; Dimitrios M. Thilikos

doi:10.1007/s00224-011-9312-0

A note on exact algorithms for vertex ordering problems on graphs

H.L. Bodlaender, F.V. Fomin, Arie M C A Koster, Dieter Kratsch, Dimitrios M. Thilikos

Research output: Contribution to journal › Article › Academic › peer-review

43 Citations (Scopus)

Abstract

In this note, we give a proof that several vertex ordering problems can be solved in O^*(2ⁿ) time and O^*(2ⁿ) space, or in O^*(4ⁿ) 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.

Original language	English
Pages (from-to)	420-432
Number of pages	13
Journal	Theory of Computing Systems
Volume	50
Issue number	3
DOIs	https://doi.org/10.1007/s00224-011-9312-0
Publication status	Published - Apr 2012
Externally published	Yes

Keywords

Algorithms
Exact algorithms
Exponential time algorithms
Graphs
Vertex ordering problems

Access to Document

10.1007/s00224-011-9312-0

Cite this

@article{7a4d19cb127042f994fe51abd5ffb581,

title = "A note on exact algorithms for vertex ordering problems on graphs",

abstract = "In this note, we give a proof that several vertex ordering problems can be solved in O*(2n) time and O*(2n) space, or in O*(4n) 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.",

keywords = "Algorithms, Exact algorithms, Exponential time algorithms, Graphs, Vertex ordering problems",

author = "H.L. Bodlaender and F.V. Fomin and Koster, {Arie M C A} and Dieter Kratsch and Thilikos, {Dimitrios M.}",

year = "2012",

month = apr,

doi = "10.1007/s00224-011-9312-0",

language = "English",

volume = "50",

pages = "420--432",

journal = "Theory of Computing Systems",

issn = "1432-4350",

publisher = "Springer New York",

number = "3",

}

TY - JOUR

T1 - A note on exact algorithms for vertex ordering problems on graphs

AU - Bodlaender, H.L.

AU - Fomin, F.V.

AU - Koster, Arie M C A

AU - Kratsch, Dieter

AU - Thilikos, Dimitrios M.

PY - 2012/4

Y1 - 2012/4

N2 - In this note, we give a proof that several vertex ordering problems can be solved in O*(2n) time and O*(2n) space, or in O*(4n) 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.

AB - In this note, we give a proof that several vertex ordering problems can be solved in O*(2n) time and O*(2n) space, or in O*(4n) 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.

KW - Algorithms

KW - Exact algorithms

KW - Exponential time algorithms

KW - Graphs

KW - Vertex ordering problems

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

U2 - 10.1007/s00224-011-9312-0

DO - 10.1007/s00224-011-9312-0

M3 - Article

AN - SCOPUS:84856222449

SN - 1432-4350

VL - 50

SP - 420

EP - 432

JO - Theory of Computing Systems

JF - Theory of Computing Systems

IS - 3

ER -

A note on exact algorithms for vertex ordering problems on graphs

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this