Isomorphism for Graphs of Bounded Connected-Path-Distance-Width

被引：0
作者：
Otachi, Yota [1 ]
机构：
[1] Japan Adv Inst Sci & Technol, Sch Informat Sci, Nomi, Ishikawa 9231292, Japan
来源：
ALGORITHMS AND COMPUTATION, ISAAC 2012 | 2012年 / 7676卷
关键词：
Graph isomorphism; Fixed-parameter tractability; Connected-path-distance-width; Treewidth; ALGORITHMS;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show that Graph Isomorphism problem (GI) can be solved in O(n(2)) time for graphs of bounded connected-path-distance-width, and more generally, in O(n(c+1)) time for graphs of bounded c-connected-path-distance-width, where n is the number of vertices. These results extend the result of Yamazaki, Bodlaender, de Fluiter, and Thilikos [Isomorphism for graphs of bounded distance width. Algorithmica 24, 105-127 (1999)], who showed the fixed-parameter tractability of GI parameterized by rooted-path-distance-width.
引用
收藏
页码：455 / 464
页数：10
相关论文
共 50 条
  • [1] Isomorphism for graphs of bounded distance width
    Yamazaki, K
    Bodlaender, HL
    de Fluiter, B
    Thilikos, DM
    ALGORITHMICA, 1999, 24 (02) : 105 - 127
  • [2] An Improved Isomorphism Test for Bounded-tree-width Graphs
    Grohe, Martin
    Neuen, Daniel
    Schweitzer, Pascal
    Wiebking, Daniel
    ACM TRANSACTIONS ON ALGORITHMS, 2020, 16 (03)
  • [3] Efficient frequent connected subgraph mining in graphs of bounded tree-width
    Horvath, Tamas
    Ramon, Jan
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (31-33) : 2784 - 2797
  • [4] Canonizing Graphs of Bounded Tree Width in Logspace
    Elberfeld, Michael
    Schweitzer, Pascal
    33RD SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2016), 2016, 47
  • [5] Restricted space algorithms for isomorphism on bounded treewidth graphs
    Das, Bireswar
    Toran, Jacobo
    Wagner, Fabian
    INFORMATION AND COMPUTATION, 2012, 217 : 71 - 83
  • [6] RESTRICTED SPACE ALGORITHMS FOR ISOMORPHISM ON BOUNDED TREEWIDTH GRAPHS
    Das, Bireswar
    Toran, Jacobo
    Wagner, Fabian
    27TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2010), 2010, 5 : 227 - 238
  • [7] Constrained-Path Labellings on Graphs of Bounded Clique-Width
    Bruno Courcelle
    Andrew Twigg
    Theory of Computing Systems, 2010, 47 : 531 - 567
  • [8] Constrained-Path Labellings on Graphs of Bounded Clique-Width
    Courcelle, Bruno
    Twigg, Andrew
    THEORY OF COMPUTING SYSTEMS, 2010, 47 (02) : 531 - 567
  • [9] ON 3-CONNECTED GRAPHS OF PATH-WIDTH AT MOST THREE
    Ding, Guoli
    Dziobiak, Stan
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (03) : 1514 - 1526
  • [10] Induced Minor Free Graphs: Isomorphism and Clique-Width
    Belmonte, Remy
    Otachi, Yota
    Schweitzer, Pascal
    ALGORITHMICA, 2018, 80 (01) : 29 - 47
12345