Pathwidth of cubic graphs and exact algorithms

被引：47
作者：
Fomin, FV [1 ]
Hoie, K [1 ]
机构：
[1] Univ Bergen, Dept Informat, N-5020 Bergen, Norway
来源：
INFORMATION PROCESSING LETTERS | 2006年 / 97卷 / 05期
关键词：
treewidth; pathwidth; cubic graph; exact exponential algorithm; maximum independent set; max-cut; minimum dominating set; graph algorithms;
D O I：
10.1016/j.ipl.2005.10.012
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We prove that for any epsilon > 0 there exists an integer n(epsilon) such that the pathwidth of every cubic (or 3-regular) graph on n > n(epsilon) vertices is at most (1/6 + epsilon)n. Based on this bound we improve the worst case time analysis for a number of exact exponential algorithms on graphs of maximum vertex degree three. (c) 2005 Elsevier B.V. All rights reserved.
引用
收藏
页码：191 / 196
页数：6
相关论文
共 26 条
[1]   Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs [J].
Alber, J ;
Bodlaender, HL ;
Fernau, H ;
Kloks, T ;
Niedermeier, R .
ALGORITHMICA, 2002, 33 (04) :461-493
[2]  
Beigel R., 1999, P 10 ANN ACM SIAM S, P856
[3]   New spectral lower bounds on the bisection width of graphs [J].
Bezrukov, S ;
Elsässer, R ;
Monien, B ;
Preis, R ;
Tillich, JP .
THEORETICAL COMPUTER SCIENCE, 2004, 320 (2-3) :155-174
[4]   A partial k-arboretum of graphs with bounded treewidth [J].
Bodlaender, HL .
THEORETICAL COMPUTER SCIENCE, 1998, 209 (1-2) :1-45
[5]  
Chen J, 2003, LECT NOTES COMPUT SC, V2906, P148
[6]   THE VERTEX SEPARATION AND SEARCH NUMBER OF A GRAPH [J].
ELLIS, JA ;
SUDBOROUGH, IH ;
TURNER, JS .
INFORMATION AND COMPUTATION, 1994, 113 (01) :50-79
[7]  
Fomin FV, 2004, LECT NOTES COMPUT SC, V3353, P245
[8]  
Fomin FV, 2005, LECT NOTES COMPUT SC, V3580, P191
[9]  
Fomin FV, 2004, LECT NOTES COMPUT SC, V2996, P56
[10]   Worst-case upper bounds for MAX-2-SAT with an application to MAX-CUT [J].
Gramm, J ;
Hirsch, EA ;
Niedermeier, R ;
Rossmanith, P .
DISCRETE APPLIED MATHEMATICS, 2003, 130 (02) :139-155
123