The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance

DOI10.1137/S009753970445603zbMath1079.68072OpenAlexW2037789547MaRDI QIDQ5317189

Eldar Fischer

Publication date: 16 September 2005

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970445603

zbMATH Keywords

regularity lemmaproperty testinggraph isomorphism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (5)

On the density of a graph and its blowup ⋮ Hypergraph regularity and random sampling ⋮ Deterministic vs non-deterministic graph property testing ⋮ The effect of induced subgraphs on quasi-randomness ⋮ A unified framework for testing linear‐invariant properties

This page was built for publication: The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance