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 journalArticleAcademicpeer-review

35 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)420-432
Number of pages13
JournalTheory of Computing Systems
Volume50
Issue number3
DOIs
Publication statusPublished - Apr 2012
Externally publishedYes

Keywords

  • Algorithms
  • Exact algorithms
  • Exponential time algorithms
  • Graphs
  • Vertex ordering problems

Fingerprint Dive into the research topics of 'A note on exact algorithms for vertex ordering problems on graphs'. Together they form a unique fingerprint.

Cite this