You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
title = {A Note on Exact Algorithms for Vertex Ordering Problems on Graphs},
journal = {Theory of Computing Systems},
year = {2012},
month = {Apr},
day = {01},
volume = {50},
number = {3},
pages = {420-432},
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.},