Graph isomorphism, general remarks | Zendy

Gary L. Miller | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Graph isomorphism, general remarks

Author(s) -

Gary L. Miller

Publication year - 1977

Publication title -

ur research (university of rochester)

Language(s) - English

Resource type - Conference proceedings

DOI - 10.1145/800105.803404

Subject(s) - graph isomorphism , isomorphism (crystallography) , computer science , graph automorphism , graph , combinatorics , mathematics , theoretical computer science , voltage graph , line graph , crystallography , crystal structure , chemistry

An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative computational complexity of generalizations and restrictions of the graph isomorphism problem. In the first Section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say Tarski models from logic). Then we show that valence seems to be important. Finally we analyze symmetric cubic graphs.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research