Isomorphism Testing for Graphs of Bounded Rank Width

2015/05/14 by Grohe, Martin, Schweitzer, Pascal · 1 citation
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1505.03737

Abstract

We give an algorithm that, for every fixed k, decides isomorphism of graphs of rank width at most k in polynomial time. As the clique width of a graph is bounded in terms of its rank width, we also obtain a polynomial time isomorphism test for graph classes of bounded clique width.

Cited by

• Parameterized Algorithms for Spanning Tree Isomorphism by Redundant Set Size

Related

• Polynomial-time Algorithm for Isomorphism of Graphs with Clique-width at\n most Three
• Polynomial Time Algorithm for Graph Isomorphism Testing
• The polynomial algorithm for graphs' isomorphism testing
• An improved isomorphism test for bounded-tree-width graphs
• Isomorphism of graphs-a polynomial test