Graph Isomorphism Complete
المؤلف:
Garey, M. R. and Johnson, D. S
المصدر:
Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman
الجزء والصفحة:
...
10-4-2022
1796
Graph Isomorphism Complete
There exists no known P algorithm for graph isomorphism testing, although the problem has also not been shown to be NP-complete. In fact, the problem of identifying isomorphic graphs seems to fall in a crack between P and NP-complete, if such a crack exists (Skiena 1990, p. 181), and as a result, the problem is sometimes assigned to a special graph isomorphism complete complexity class.
REFERENCES
Garey, M. R. and Johnson, D. S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, pp. 155-156, 1983.
Skiena, S. "Graph Isomorphism." §5.2 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 181-187, 1990.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
