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 条
  • [21] Embeddings of k-connected graphs of pathwidth k
    Gupta, A
    Nishimura, N
    Proskurowski, A
    Ragde, P
    DISCRETE APPLIED MATHEMATICS, 2005, 145 (02) : 242 - 265
  • [22] Exact and approximate algorithms for movement problems on (special classes of) graphs
    Bilo, Davide
    Guala, Luciano
    Leucci, Stefano
    Proietti, Guido
    THEORETICAL COMPUTER SCIENCE, 2016, 652 : 86 - 101
  • [23] The List Coloring Reconfiguration Problem for Bounded Pathwidth Graphs
    Hatanaka, Tatsuhiko
    Ito, Takehiro
    Zhou, Xiao
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2015, E98A (06): : 1168 - 1178
  • [24] Some Reduction Procedure for Computing Pathwidth of Undirected Graphs
    Ikeda, Masataka
    Nagamochi, Hiroshi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2015, E98D (03): : 503 - 511
  • [25] Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth
    Dyer, Martin
    Greenhill, Catherine
    Mueller, Haiko
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2019), 2019, 11789 : 298 - 310
  • [26] Counting independent sets in graphs with bounded bipartite pathwidth
    Dyer, Martin
    Greenhill, Catherine
    Muller, Haiko
    RANDOM STRUCTURES & ALGORITHMS, 2021, 59 (02) : 204 - 237
  • [27] New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs
    Babenko, Maxim
    Gusakov, Alexey
    28TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2011), 2011, 9 : 519 - 530
  • [28] Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
    Dorn F.
    Penninkx E.
    Bodlaender H.L.
    Fomin F.V.
    Algorithmica (New York), 2010, 58 (03): : 790 - 810
  • [29] On Exact Algorithms for Treewidth
    Bodlaender, Hans L.
    Fomin, Fedor V.
    Koster, Arie M. C. A.
    Kratsch, Dieter
    Thilikos, Dimitrios M.
    ACM TRANSACTIONS ON ALGORITHMS, 2012, 9 (01)
  • [30] Lower bounds on the pathwidth of some grid-like graphs
    Ellis, John
    Warren, Robert
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (05) : 545 - 555
12345