Circle graph isomorphism and canonization can be solved in O((n+m)α(n+m)) time using minimal split decomposition and linear-time canonization of split trees.
Testing isomorphism of circular-arc graphs in polynomial time
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
A graph is said to be circular-arc if the vertices can be associated with arcs of a circle so that two vertices are adjacent if and only if the corresponding arcs overlap. It is proved that the isomorphism of circular-arc graphs can be tested by the Weisfeiler-Leman algorithm after individualization of two vertices.
fields
cs.DS 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Circle Graph Isomorphism in Almost Linear Time
Circle graph isomorphism and canonization can be solved in O((n+m)α(n+m)) time using minimal split decomposition and linear-time canonization of split trees.