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