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 条
  • [31] Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques
    Kaplan, H
    Shamir, R
    SIAM JOURNAL ON COMPUTING, 1996, 25 (03) : 540 - 561
  • [32] Exact Algorithms for Annotated Edge Dominating Set in Graphs with Degree Bounded by 3
    Xiao, Mingyu
    Nagamochi, Hiroshi
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, 2013, E96D (03): : 408 - 418
  • [33] Exact Algorithms for Maximum Weighted Independent Set on Sparse Graphs (Extended Abstract)
    Huang, Sen
    Xiao, Mingyu
    Chen, Xiaoyu
    COMPUTING AND COMBINATORICS (COCOON 2021), 2021, 13025 : 617 - 628
  • [34] Hardness results, approximation and exact algorithms for liar's domination problem in graphs
    Panda, B. S.
    Paul, S.
    Pradhan, D.
    THEORETICAL COMPUTER SCIENCE, 2015, 573 : 26 - 42
  • [35] 2-Connecting outerplanar graphs without blowing up the pathwidth
    Babu, Jasine
    Basavaraju, Manu
    Chandran, L. Sunil
    Rajendraprasad, Deepak
    THEORETICAL COMPUTER SCIENCE, 2014, 554 : 119 - 134
  • [36] Generation of Cubic graphs
    Brinkmann, Gunnar
    Goedgebeur, Jan
    Mckay, Brendan D.
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2011, 13 (02): : 69 - 79
  • [37] Decycling cubic graphs
    Nedela, Roman
    Seifrtova, Michaela
    Skoviera, Martin
    DISCRETE MATHEMATICS, 2024, 347 (08)
  • [38] Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2
    Golovach, Petr A.
    Heggernes, Pinar
    Kratsch, Dieter
    Lima, Paloma T.
    Paulusma, Daniel
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE (WG 2017), 2017, 10520 : 275 - 288
  • [39] Parallel algorithms for series parallel graphs and graphs with treewidth two
    Bodlaender, HL
    van Antwerpen-de Fluiter, B
    ALGORITHMICA, 2001, 29 (04) : 534 - 559
  • [40] Approximation algorithms for clique-transversal sets and clique-independent sets in cubic graphs
    Liang, Zuosong
    Shan, Erfang
    INFORMATION PROCESSING LETTERS, 2011, 111 (23-24) : 1104 - 1107
12345