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 条

[31] Rank-width and tree-width of H-minor-free graphs
Fomin, Fedor V.
Oum, Sang-il
Thilikos, Dimitrios M.
EUROPEAN JOURNAL OF COMBINATORICS, 2010, 31 (07) : 1617 - 1628
[32] Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
IARCS ANNUAL CONFERENCE ON FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE (FSTTCS 2010), 2010, 8 : 73 - 83
[33] Better Algorithms for Satisfiability Problems for Formulas of Bounded Rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
FUNDAMENTA INFORMATICAE, 2013, 123 (01) : 59 - 76
[34] Conflict-Free Coloring: Graphs of Bounded Clique-Width and Intersection Graphs
Bhyravarapu, Sriram
Hartmann, Tim A.
Hoang, Hung P.
Kalyanasundaram, Subrahmanyam
Reddy, I. Vinod
ALGORITHMICA, 2024, 86 (07) : 2250 - 2288
[35] MSOL partitioning problems on graphs of bounded treewidth and clique-width
Rao, Michael
THEORETICAL COMPUTER SCIENCE, 2007, 377 (1-3) : 260 - 267
[36] Constrained-Path Labellings on Graphs of Bounded Clique-Width
Bruno Courcelle
Andrew Twigg
Theory of Computing Systems, 2010, 47 : 531 - 567
[37] Constrained-Path Labellings on Graphs of Bounded Clique-Width
Courcelle, Bruno
Twigg, Andrew
THEORY OF COMPUTING SYSTEMS, 2010, 47 (02) : 531 - 567
[38] Chordal bipartite graphs of bounded tree- and clique-width
Lozin, V
Rautenbach, D
DISCRETE MATHEMATICS, 2004, 283 (1-3) : 151 - 158
[39] Optimal Centrality Computations Within Bounded Clique-Width Graphs
Guillaume Ducoffe
Algorithmica, 2022, 84 : 3192 - 3222
[40] Optimal Centrality Computations Within Bounded Clique-Width Graphs
Ducoffe, Guillaume
ALGORITHMICA, 2022, 84 (11) : 3192 - 3222

← 1 2 3 4 5 →