A Note on Exact Algorithms for Vertex Ordering Problems on Graphs

被引：0

作者：

Hans L. Bodlaender

Fedor V. Fomin

Arie M. C. A. Koster

Dieter Kratsch

Dimitrios M. Thilikos

机构：

[1] Utrecht University,Department of Information and Computing Sciences

[2] University of Bergen,Department of Informatics

[3] RWTH Aachen University,Lehrstuhl II für Mathematik

[4] Université de Metz,LITA

[5] National and Kapodistrian University of Athens,Department of Mathematics

来源：

Theory of Computing Systems | 2012年 / 50卷

关键词：

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

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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.

引用

页码：420 / 432

页数：12

共 23 条

[1]

Bodlaender H.L.(1998)A partial Theor. Comput. Sci. 209 1-45

[2]

Clautiaux F.(2004)-arboretum of graphs with bounded treewidth RAIRO Oper. Res. 38 13-26

[3]

Moukrim A.(1997)Heuristic and meta-heuristic methods for computing graph treewidth Theor. Comput. Sci. 172 233-254

[4]

Négre S.(2002)Fugitive-search games on graphs and related parameters ACM Comput. Surv. 34 313-356

[5]

Carlier J.(2008)A survey of graph layout problems SIAM J. Comput. 38 1058-1079

[6]

Dendris N.D.(1976)Exact algorithms for treewidth and minimum fill-in Theor. Comput. Sci. 1 237-267

[7]

Kirousis L.M.(1987)Some simplified NP-complete graph problems SIAM J. Comput. 16 486-502

[8]

Thilikos D.M.(1962)Expected computation time for Hamiltonian path problem J. Soc. Ind. Appl. Math. 10 196-210

[9]

Díaz J.(1992)A dynamic programming approach to sequencing problems Inf. Process. Lett. 42 345-350

[10]

Petit J.(undefined)The vertex separation number of a graph equals its path width undefined undefined undefined-undefined

← 1 2 3 →