Research · Graph theory

Graph Isomorphism

A layered labeling approach to decide whether two graphs are the same up to node relabeling — with extensive empirical testing on 470,000+ instances.

Layers approach

Each node gets a structural label built from neighborhood layers (degree, incident edges, internal structure). Labels are compared across two graphs; a consistent bijection yields SIMILAR. The Java implementation lives in src/graphiso.

• Fast reject: node count, edge count, degree histogram
• Per-node labels via generate_label
• Tree reconstruction from labels for verification

Benchmark coverage

4–50 nodes~4,700
51–100 nodes~50
101–400 nodes~300+
Total reported470,000+

Full result files ship in the merged repo under benchmark-results/.

Source repositories

Algorithm publication is planned after formal proof. This page documents the method and lets you explore output format and small-graph checks.