Testing Graph Isomorphism

DOI10.1137/070680795MaRDI QIDQ3614155zbMATH OpenOpenAlexFDO

Authors Eldar Fischer, Arie Matsliah

Publication date 16 March 2009

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

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

zbMATH Keywords

approximationgraph isomorphismproperty testing

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20)

Recommendations

• The query complexity of graph isomorphism: bypassing distribution testing lower bounds
• scientific article; zbMATH DE number 1241385
• Property testing in bounded degree graphs
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• The difficulty of testing for isomorphism against a graph that is given in advance

Cited in

(15)

• Robustly self-ordered graphs: constructions and applications to property testing
• TESTING EMBEDDABILITY BETWEEN METRIC SPACES
• Testing distributions of huge objects
• Generic case complexity of the graph isomorphism problem
• Sublinear algorithms in the external memory model
• Hierarchy theorems for property testing
• The query complexity of graph isomorphism: bypassing distribution testing lower bounds
• Robustly self-ordered graphs: constructions and applications to property testing
• The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance
• Distributed Testing of Graph Isomorphism in the CONGEST Model.
• On testing isomorphism to a fixed graph in the bounded-degree graph model
• Testing isomorphism in the bounded-degree graph model
• The difficulty of testing for isomorphism against a graph that is given in advance
• Efficient Method to Perform Isomorphism Testing of Labeled Graphs
• Testing forest-isomorphism in the adjacency list model

This page was built for publication: Testing Graph Isomorphism

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