Testing isomorphism in the bounded-degree graph model

DOI10.1007/978-3-031-88946-2_16MaRDI QIDQ6877272zbMATH OpenFDO

Authors Oded Goldreich

Publication date 8 January 2026

Full work available at URL https://doi.org/10.1007/978-3-031-88946-2_16

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68Wxx)

Cites work

• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Distribution testing lower bounds via reductions from communication complexity
• Every property of hyperfinite graphs is testable
• Introduction to Property Testing
• On Proximity-Oblivious Testing
• Property testing and its connection to learning and approximation
• Property testing in bounded degree graphs
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Testing forest-isomorphism in the adjacency list model
• Testing Graph Isomorphism
• Testing the diameter of graphs
• The isoperimetric number of random regular graphs
• Tight Bounds for Testing Bipartiteness in General Graphs

Cited in

(1)

• Testing in the bounded-degree graph model with degree bound two

This page was built for publication: Testing isomorphism in the bounded-degree graph model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6877272)