Isomorphism Testing for Graphs of Bounded Rank Width

被引：27
|
作者：
Grohe, Martin [1 ]
Schweitzer, Pascal [1 ]
机构：
[1] Rhein Westfal TH Aachen, Aachen, Germany
来源：
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2015年
关键词：
CLIQUE-WIDTH; ALGORITHM;
D O I：
10.1109/FOCS.2015.66
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the rank width of a graph is bounded in terms of its clique width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.
引用
收藏
页码：1010 / 1029
页数：20
相关论文
共 50 条
  • [41] On the OBDD size for graphs of bounded tree- and clique-width
    Meer, Klaus
    Rautenbach, Dieter
    DISCRETE MATHEMATICS, 2009, 309 (04) : 843 - 851
  • [42] Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width
    Ducoffe, Guillaume
    ALGORITHMICA, 2022, 84 (11) : 3489 - 3520
  • [43] Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
    Frank Gurski
    Carolin Rehs
    Mathematical Methods of Operations Research, 2019, 89 : 411 - 432
  • [44] An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width
    Bergougnoux, Benjamin
    Kante, Mamadou Moustapha
    Kwon, O-joung
    ALGORITHMICA, 2020, 82 (06) : 1654 - 1674
  • [45] An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width
    Benjamin Bergougnoux
    Mamadou Moustapha Kanté
    O-joung Kwon
    Algorithmica, 2020, 82 : 1654 - 1674
  • [46] Subset Glauber dynamics on graphs, hypergraphs and matroids of bounded tree-width
    Bordewich, Magnus
    Kang, Ross J.
    ELECTRONIC JOURNAL OF COMBINATORICS, 2014, 21 (04)
  • [47] Fully Polynomial FPT Algorithms for Some Classes of Bounded Clique-width Graphs
    Coudert, David
    Ducoffe, Guillaume
    Popa, Alexandru
    ACM TRANSACTIONS ON ALGORITHMS, 2019, 15 (03)
  • [48] Monoidal Width: Capturing Rank Width
    Di Lavore, Elena
    Sobocinski, Pawel
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2023, (380): : 268 - 283
  • [49] Maximal Matching and Path Matching Counting in Polynomial Time for Graphs of Bounded Clique Width
    de Menibus, Benjamin Hellouin
    Uno, Takeaki
    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 2011, 6648 : 483 - 494
  • [50] On the band-, tree-, and clique-width of graphs with bounded vertex degree
    Lozin, V
    Rautenbach, D
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) : 195 - 206
12345