A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

作者：Bodlaender Hans L^*; Fomin Fedor V; Koster Arie M C A; Kratsch Dieter; Thilikos Dimitrios M

来源：Theory of Computing Systems, 2012, 50(3): 420-432.

DOI：10.1007/s00224-011-9312-0

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

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

• 出版日期2012-4