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 条

[1] Canonisation and Definability for Graphs of Bounded Rank Width
Grohe, Martin
Neuen, Daniel
ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2023, 24 (01)
[2] Canonisation and Definability for Graphs of Bounded Rank Width
Grohe, Martin
Neuen, Daniel
2019 34TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2019,
[3] Better Polynomial Algorithms on Graphs of Bounded Rank-Width
Ganian, Robert
Hlineny, Petr
COMBINATORIAL ALGORITHMS, 2009, 5874 : 266 - 277
[4] On NC algorithms for problems on bounded rank-width graphs
Das, Bireswar
Dasgupta, Anirban
Enduri, Murali Krishna
Reddy, I. Vinod
INFORMATION PROCESSING LETTERS, 2018, 139 : 64 - 67
[5] A unified approach to polynomial algorithms on graphs of bounded (bi-)rank-width
Ganian, Robert
Hlineny, Petr
Obdrzalek, Jan
EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (03) : 680 - 701
[6] Rank-width of random graphs
Lee, Choongbum
Lee, Joonkyung
Oum, Sang-il
JOURNAL OF GRAPH THEORY, 2012, 70 (03) : 339 - 347
[7] On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width
Ganian, Robert
Hlineny, Petr
DISCRETE APPLIED MATHEMATICS, 2010, 158 (07) : 851 - 867
[8] Alliances in graphs of bounded clique-width
Kiyomi, Masashi
Otachi, Yota
DISCRETE APPLIED MATHEMATICS, 2017, 223 : 91 - 97
[9] Line graphs of bounded clique-width
Gurski, Frank
Wanke, Egon
DISCRETE MATHEMATICS, 2007, 307 (22) : 2734 - 2754
[10] Induced Minor Free Graphs: Isomorphism and Clique-Width
Belmonte, Remy
Otachi, Yota
Schweitzer, Pascal
ALGORITHMICA, 2018, 80 (01) : 29 - 47

← 1 2 3 4 5 →