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 条

[11] Induced Minor Free Graphs: Isomorphism and Clique-Width
Rémy Belmonte
Yota Otachi
Pascal Schweitzer
Algorithmica, 2018, 80 : 29 - 47
[12] Polynomial-time algorithm for isomorphism of graphs with clique-width at most three
Das, Bireswar
Enduri, Murali Krishna
Reddy, I. Vinod
THEORETICAL COMPUTER SCIENCE, 2020, 819 (819) : 9 - 23
[13] On powers of graphs of bounded NLC-width (clique-width)
Suchana, Karol
Todinca, Ioan
DISCRETE APPLIED MATHEMATICS, 2007, 155 (14) : 1885 - 1893
[14] A LINEAR-TIME ALGORITHM FOR ISOMORPHISM OF GRAPHS OF BOUNDED AVERAGE GENUS
CHEN, JN
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (04) : 614 - 631
[15] Critical properties of graphs of bounded clique-width
Lozin, Vadim V.
Milanic, Martin
DISCRETE MATHEMATICS, 2013, 313 (09) : 1035 - 1044
[16] The Rank-Width of Edge-Coloured Graphs
Kante, Mamadou Moustapha
Rao, Michael
THEORY OF COMPUTING SYSTEMS, 2013, 52 (04) : 599 - 644
[17] The Rank-Width of Edge-Coloured Graphs
Mamadou Moustapha Kanté
Michael Rao
Theory of Computing Systems, 2013, 52 : 599 - 644
[18] Recent developments on graphs of bounded clique-width
Kaminski, Marcin
Lozin, Vadim V.
Milanic, Martin
DISCRETE APPLIED MATHEMATICS, 2009, 157 (12) : 2747 - 2761
[19] Solving Problems on Graphs of High Rank-Width
Eiben, Eduard
Ganian, Robert
Szeider, Stefan
ALGORITHMICA, 2018, 80 (02) : 742 - 771
[20] Several notions of rank-width for countable graphs
Courcelle, Bruno
JOURNAL OF COMBINATORIAL THEORY SERIES B, 2017, 123 : 186 - 214

← 1 2 3 4 5 →