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 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. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/FOCS.2015.66 | IEEE Symposium on Foundations of Computer Science |
Keywords | Field | DocType |
graph isomorphism,connectivity functions,canonical decomposition theorems,rank width,clique width | Discrete mathematics,Block graph,Combinatorics,Graph isomorphism,Clique graph,Induced subgraph isomorphism problem,Isomorphism,Clique-width,Mathematics,Subgraph isomorphism problem,Bounded function | Journal |
Volume | ISSN | Citations |
abs/1505.03737 | 0272-5428 | 18 |
PageRank | References | Authors |
0.72 | 27 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Grohe | 1 | 2280 | 127.40 |
Pascal Schweitzer | 2 | 214 | 16.94 |