The graph isomorphism disease.

*(English)*Zbl 0381.05026##### MSC:

05C10 | Planar graphs; geometric and topological aspects of graph theory |

05-04 | Software, source code, etc. for problems pertaining to combinatorics |

68W99 | Algorithms in computer science |

68R10 | Graph theory (including graph drawing) in computer science |

PDF
BibTeX
XML
Cite

\textit{R. C. Read} and \textit{D. G. Corneil}, J. Graph Theory 1, 339--363 (1977; Zbl 0381.05026)

Full Text:
DOI

**OpenURL**

##### References:

[1] | , and , The Design and Analysis of Computer Algorithms. Addison-Wesley, Reading, Mass. (1974). |

[2] | Balaban, J. Chem. Documentation 11 pp 258– (1971) |

[3] | Problems polynomially equivalent to graph isomorphism. Proceedings of the Symposium on New Directions and Recent Results in Algorithms and Complexity. Carnegie-Mellon University (April 1976). |

[4] | and , Linear algorithms to recognize interval graphs and test for consecutive ones property. Proceedings of the 7th Annual ACM Symposium on the Theory of Computing. (May 1975) 255–265. |

[5] | Computational Complexity: theory and practice. Currents in the Theory of Computing. Ed. Prentice-Hall, Englewood Cliffs, N. J. (1973) 35–89. |

[6] | and , Symmetric Hadamard Matrices of order 36. T. H.-report 70-WSK-02. Department of Mathematics, Technological University, Eindhoven, Netherlands (1970). |

[7] | Collatz, Abh. Math. Sem. Univ. Hamburg 21 pp 63– (1957) |

[8] | The complexity of theorem-proving procedures. Proceedings Third Annual ACM Symposium on the Theory of Computing (1971) 151–158. |

[9] | Graph Isomorphism. Ph.D. Thesis. University of Toronto (1968). Available as a Department of Computer Science Technical Report. |

[10] | The analysis of graph theoretical algorithms. Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory & Computing. et al., Eds. Utilitas Mathematica, Winnipeg (1974) 3–38. |

[11] | Corneil, J. Assoc. Comput. Mach. 17 pp 51– (1970) · Zbl 0199.27801 |

[12] | and , Algorithmic techniques for the generation and analysis of strongly regular graphs and other combinatorial configurations. Algebraic Aspects of Combinatorics (Qualicum Beach, B. C., May 1976). Proceedings to appear. |

[13] | Computing techniques for the construction and analysis of block designs. Ph.D. Thesis. Department of Computer Science, University of Toronto (1976). Available as a Department of Computer Science Technical Report. |

[14] | The four color conjecture and other graphical diseases. Proof Techniques in Graph Theory. Ed. Academic Press, New York (1969) 1–10. |

[15] | Graph Theory. Addison Wesley, Reading, Mass. (1971). |

[16] | Harary, Bull. London Math. Soc. 3 pp 321– (1971) |

[17] | and , Isomorphism of planar graphs. Complexity of Computer Computations. and , Eds. Plenum, New York (1972) 131–152. |

[18] | and , Linear time algorithm for isomorphism of planar graphs (extended abstract). Sixth Annual ACM Symposium on Theory of Computing, Seattle (May 1974). |

[19] | Reducibility among combinatorial problems. Complexity of Computer Computations. and , Eds. Plenum, New York (1972) 85–103. |

[20] | Karp, Networks 5 pp 45– (1975) |

[21] | The fast approximate solution of hard combinatorial problems. Proceedings 6th South-Eastern Conference on Combinatorics, Graph Theory and Computing. et al., Eds. Utilitas Mathematica, Winnipeg (1975) 15–31. |

[22] | Knödel, Computing 8 pp 329– (1971) |

[23] | Kudo, J. Chem. Documentation 13 pp 225– (1973) |

[24] | Graph isomorphism using vertex adjacency matrices. Proceedings of the 25th Summer Meeting Canadian Mathematical Congress, Lakehead University (1971) 471–476. |

[25] | The Theory of Group Characters. Oxford University Press, Oxford. (1950). |

[26] | Sample graphs for graph isomorphism testing. To appear as a technical report, Department of Computer Science, University of Toronto. |

[27] | Moon, Israel J. Math. 3 pp 123– (1965) |

[28] | Morgan, J. Chem. Documentation 5 pp 107– (1965) |

[29] | Nagle, J. Math. Phys. 7 pp 1588– (1966) |

[30] | and , Graph isomorphism and the coding of graphs. Research Report UWI/CC5, University of the West Indies, Jamica (1967). |

[31] | Sirovich, Calcolo 8 pp 301– (1971) |

[32] | Spialter, J. Amer. Chem. Soc. 85 pp 2012– (1963) |

[33] | Spialter, J. Chem. Documentation 4 pp 261– (1964) |

[34] | Spialter, J. Chem. Documentation 4 pp 269– (1964) |

[35] | Turner, SIAM J. Appl. Math. 16 pp 520– (1968) |

[36] | Unger, Comm. ACM 7 pp 26– (1964) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.