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 条
  • [21] The NLC-width and clique-width for powers of graphs of bounded tree-width
    Gurski, Frank
    Wanke, Egon
    DISCRETE APPLIED MATHEMATICS, 2009, 157 (04) : 583 - 595
  • [22] Solutions for the knapsack problem with conflict and forcing graphs of bounded clique-width
    Gurski, Frank
    Rehs, Carolin
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 2019, 89 (03) : 411 - 432
  • [23] A local characterization of bounded clique-width for line graphs
    Gurski, Frank
    Wanke, Egon
    DISCRETE MATHEMATICS, 2007, 307 (06) : 756 - 759
  • [24] Vertex disjoint paths on clique-width bounded graphs
    Gurski, Frank
    Wanke, Egon
    THEORETICAL COMPUTER SCIENCE, 2006, 359 (1-3) : 188 - 199
  • [25] Computing the Tutte polynomial on graphs of bounded clique-width
    Giménez, O
    Hlineny, P
    Noy, M
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2005, 3787 : 59 - 68
  • [26] Computing the tutte polynomial on graphs of bounded clique-width
    Gimenez, Omer
    Hlineny, Petr
    Noy, Marc
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (04) : 932 - 946
  • [27] On rank-width of (diamond, even hole)-free graphs
    Adler, Isolde
    Le, Ngoc Khang
    Mueller, Haiko
    Radovanovic, Marko
    Trotignon, Nicolas
    Vuskovic, Kristina
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2017, 19 (01)
  • [28] Graphs of bounded depth-2 rank-brittleness
    Kwon, O-joung
    Oum, Sang-il
    JOURNAL OF GRAPH THEORY, 2021, 96 (03) : 361 - 378
  • [29] Linear Rank-Width of Distance-Hereditary Graphs
    Adler, Isolde
    Kante, Mamadou Moustapha
    Kwon, O-joung
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2014, 8747 : 42 - 55
  • [30] On rank-width of (diamond, even hole)-free graphs
    Adler I.
    Le N.K.
    Müller H.
    Radovanović M.
    Trotignon N.
    Vušković K.
    Discrete Math. Theor. Comput. Sci., 1
12345