Idioma:

Graph isomorphism, general remarks

Miller, Gary L.

Proceedings of the ninth annual ACM symposium on Theory of computing, 1977, p.143-150 [Periódico revisado por pares]

Sem texto completo

Citações Citado por

Título:
Graph isomorphism, general remarks
Autor: Miller, Gary L.
Assuntos: Mathematics of computing -- Discrete mathematics -- Graph theory -- Paths and connectivity problems ; Theory of computation -- Computational complexity and cryptography -- Interactive proof systems ; Theory of computation -- Computational complexity and cryptography -- Proof complexity ; Theory of computation -- Logic -- Proof theory ; Theory of computation -- Randomness, geometry and discrete structures
É parte de: Proceedings of the ninth annual ACM symposium on Theory of computing, 1977, p.143-150
Descrição: 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.
Editor: New York, NY, USA: ACM
Idioma: Inglês

Voltar para lista de resultados

Anterior Resultado 7 Avançar Ir para próxima página