Isomorphism Testing in Hookup Classes
Authors:
- M. M. KlaweMKM. M. Klawe
- D. G. CorneilDCD. G. Corneil
- A. ProskurowskiAPA. Proskurowski
- 1 June 1982
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 3 (2) , 260-274
Abstract
Hookup classes are classes of graphs with a certain type of recursive definition, which can be viewed as a generalization of k-trees. We show that many hookup classes of graphs are isomorphism complete, and give polynomial isomorphism algorithms for the others. Other results in this paper include the development of a structural decomposition for hookup graphs and similar isomorphism results for generalizations of hookup classes, including a polynomial isomorphism testing algorithm for chordal graphs with bounded maximum clique size.Keywords
This publication has 8 references indexed in Scilit:
- Networks immune to isolated failuresNetworks, 1981
- Isomorphism of graphs of bounded valence can be tested in polynomial time1980
- A polynomial-time algorithm for determining the isomorphism of graphs of fixed genus1980
- Isomorphism testing for graphs of bounded genus1980
- The graph isomorphism diseaseJournal of Graph Theory, 1977
- On simple characterizations of k-treesDiscrete Mathematics, 1974
- Linear time algorithm for isomorphism of planar graphs (Preliminary Report)1974
- Incidence matrices and interval graphsPacific Journal of Mathematics, 1965