𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graph 2-isomorphism is NP-complete

✍ Scribed by P.Frances Yao

Book ID
113162136
Publisher
Elsevier Science
Year
1979
Tongue
English
Weight
532 KB
Volume
9
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Graph Isomorphism is in SPP
Graph Isomorphism is in SPP
✍ V. Arvind; Piyush P. Kurur πŸ“‚ Article πŸ“… 2006 πŸ› Elsevier Science 🌐 English βš– 187 KB
Completeness results for graph isomorphi
Completeness results for graph isomorphism
✍ Birgit Jenner; Johannes KΓΆbler; Pierre McKenzie; Jacobo TorΓ‘n πŸ“‚ Article πŸ“… 2003 πŸ› Elsevier Science 🌐 English βš– 239 KB

We prove that the graph isomorphism problem restricted to trees and to colored graphs with color multiplicities 2 and 3 is many-one complete for several complexity classes within NC 2 . In particular we show that tree isomorphism, when trees are encoded as strings, is NC 1 -hard under AC 0 -reductio