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 条
  • [1] A BOUND ON THE PATHWIDTH OF SPARSE GRAPHS WITH APPLICATIONS TO EXACT ALGORITHMS
    Kneis, Joachim
    Moelle, Daniel
    Richter, Stefan
    Rossmanith, Peter
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2009, 23 (01) : 407 - 427
  • [2] Exact Algorithms for Intervalizing Coloured Graphs
    Bodlaender, Hans L.
    van Rooij, Johan M. M.
    THEORY OF COMPUTING SYSTEMS, 2016, 58 (02) : 273 - 286
  • [3] TREEWIDTH AND PATHWIDTH OF PERMUTATION GRAPHS
    BODLAENDER, HL
    KLOKS, T
    KRATSCH, D
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 1995, 8 (04) : 606 - 616
  • [4] Exact Algorithms for Intervalizing Coloured Graphs
    Hans L. Bodlaender
    Johan M. M. van Rooij
    Theory of Computing Systems, 2016, 58 : 273 - 286
  • [5] Approximation of pathwidth of outerplanar graphs
    Bodlaender, HL
    Fomin, FV
    JOURNAL OF ALGORITHMS, 2002, 43 (02) : 190 - 200
  • [6] Pathwidth of planar and line graphs
    Fomin, FV
    GRAPHS AND COMBINATORICS, 2003, 19 (01) : 91 - 99
  • [7] Pathwidth and Searching in Parameterized Threshold Graphs
    Krishna, D. Sai
    Reddy, T. V. Thirumala
    Shashank, B. Sai
    Rangan, C. Pandu
    WALCOM: ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2010, 5942 : 293 - +
  • [8] Crossing Number for Graphs with Bounded Pathwidth
    Biedl, Therese
    Chimani, Markus
    Derka, Martin
    Mutzel, Petra
    ALGORITHMICA, 2020, 82 (02) : 355 - 384
  • [9] Approximating Pathwidth for Graphs of Small Treewidth
    Groenland, Carla
    Joret, Gwenael
    Nadara, Wojciech
    Walczak, Bartosz
    ACM TRANSACTIONS ON ALGORITHMS, 2023, 19 (02)
  • [10] Crossing Number for Graphs with Bounded Pathwidth
    Therese Biedl
    Markus Chimani
    Martin Derka
    Petra Mutzel
    Algorithmica, 2020, 82 : 355 - 384
12345