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 language | English (US) |
---|---|
Pages (from-to) | 420-432 |
Number of pages | 13 |
Journal | Theory of Computing Systems |
Volume | 50 |
Issue number | 3 |
DOIs | |
State | Published - Apr 2012 |
Keywords
- Algorithms
- Exact algorithms
- Exponential time algorithms
- Graphs
- Vertex ordering problems
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics