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
相关论文
共 50 条
  • [41] Colouring exact distance graphs of chordal graphs
    Quiroz, Daniel A.
    DISCRETE MATHEMATICS, 2020, 343 (05)
  • [42] Maximum edge-cuts in cubic graphs with large girth and in random cubic graphs
    Kardos, Frantisek
    Kral', Daniel
    Volec, Jan
    RANDOM STRUCTURES & ALGORITHMS, 2012, 41 (04) : 506 - 520
  • [43] Dynamic algorithms for graphs of bounded treewidth
    Hagerup, T
    ALGORITHMICA, 2000, 27 (3-4) : 292 - 315
  • [44] The packing number of cubic graphs
    Goddard, Wayne
    Henning, Michael A.
    DISCRETE OPTIMIZATION, 2024, 53
  • [45] Bipartite density of cubic graphs
    Berman, A
    Zhang, XD
    DISCRETE MATHEMATICS, 2003, 260 (1-3) : 27 - 35
  • [46] Decomposing planar cubic graphs
    Hoffmann-Ostenhof, Arthur
    Kaiser, Tomas
    Ozeki, Kenta
    JOURNAL OF GRAPH THEORY, 2018, 88 (04) : 631 - 640
  • [47] The Hamiltonian Number of Cubic Graphs
    Thaithae, Sermsri
    Punnim, Narong
    COMPUTATIONAL GEOMETRY AND GRAPH THEORY, 2008, 4535 : 213 - 223
  • [48] Path factors in cubic graphs
    Kawarabayashi, K
    Matsuda, H
    Oda, Y
    Ota, K
    JOURNAL OF GRAPH THEORY, 2002, 39 (03) : 188 - 193
  • [49] The decycling number of cubic graphs
    Punnim, N
    COMBINATORIAL GEOMETRY AND GRAPH THEORY, 2005, 3330 : 141 - 145
  • [50] Restrained domination in cubic graphs
    Johannes H. Hattingh
    Ernst J. Joubert
    Journal of Combinatorial Optimization, 2011, 22 : 166 - 179
12345