A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

Hans L. Bodlaender, Fedor V. Fomin, Arie M.C.A. Koster, Dieter Kratsch, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review

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 (US)
Pages (from-to)420-432
Number of pages13
JournalTheory of Computing Systems
Volume50
Issue number3
DOIs
StatePublished - Apr 2012

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

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