Testing isomorphism of circular-arc graphs in polynomial time

Ilia Ponomarenko; Peter Zeman; Roman Nedela

Testing isomorphism of circular-arc graphs in polynomial time

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1903.11062 v2 pith:ECVQ5BA7 submitted 2019-03-26 cs.DS math.CO

Roman Nedela , Ilia Ponomarenko , Peter Zeman This is my paper · ORCID

classification cs.DSmath.CO

keywords circular-arcverticesarcsgraphsisomorphismadjacentalgorithmassociated

verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments

read the original 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.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Circle Graph Isomorphism in Almost Linear Time
cs.DS 2019-08 conditional novelty 7.0 of 10

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.

Pith tools