×

A linear-time algorithm for isomorphism of a subclass of chordal graphs. (English) Zbl 0764.68136

Summary: The graph isomorphism problem has been much studied in the literature. Linear-time algorithms for the isomorphism problem have been obtained for trees, for planar graphs for maximal outerplanar graphs and for interval graphs.
We propose a linear-time algorithm for the isomorphism problem of a subclass of chordal graphs, namely, Hamiltonian 2-sep-chordal graphs. This class properly contains the class of mops. The polynomial transformation given in G. S. Lueker and K. S. Booth [J. Assoc. Comput. Machin. 26, 183-195 (1979; Zbl 0402.68050)] suffices to show that the isomorphism problem for 2-sep-chordal graphs is as hard as the general graph isomorphism problem. Consequently, it is of interest to study for what other subclasses of chordal graphs, in addition to trees, mops, and interval graphs there exist polynomial time isomorphism solutions.
In Section 2, we introduce the class of 2-sep-chordal graphs and discuss related results. Section 3 contains the linear-time isomorphism algorithm.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68Q25 Analysis of algorithms and problem complexity
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C38 Paths and cycles
05C85 Graph algorithms (graph-theoretic aspects)

Citations:

Zbl 0402.68050
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Beyer, T.; Jones, W.; Mitchell, S., Linear algorithms for isomorphism of outerplanar graphs, J. ACM, 26, 603-610 (1979) · Zbl 0413.68058
[3] Dirac, G. A., On rigid circuit graphs, Abh. Math. Sem. Univ. Hamburg, 25, 71-76 (1961) · Zbl 0098.14703
[4] Hopcroft, J. E.; Tarjan, R. E., Isomorphism of planar graphs, (Miller, R.; Thatcher, J., Complexity of Computations (1972), Plenum Press: Plenum Press New York), 143-150 · Zbl 0274.05103
[5] Hopcroft, J. E.; Wong, J. K., Linear time algorithm for isomorphism of planar graphs, Proc. Sixth STOC, 172-184 (1974) · Zbl 0369.05028
[6] Leuker, G. S.; Booth, K. S., A linear time algorithm for deciding interval graph isomorphism, J. ACM, 26, 183-195 (1979) · Zbl 0402.68050
[7] Mitchell, S. L., Linear algorithms to recognize outerplanar and maximal outerplanar graphs, Inform. Process. Lett., 9, 229-232 (1979) · Zbl 0444.68055
[8] Sreenivasa Kumar, P., Algorithmic and structural results on chordal graphs, (Ph.D. Thesis (1990), Dept. of Computer Science and Automation)
[9] Sreenivasa Kumar, P.; Veni Madhavan, C. E., A new class of separators and planarity of chordal graphs, (Proc. Ninth FST&TCS Conf., 405 (1989), Springer: Springer Berlin), 30-43, Lecture Notes in Computer Science · Zbl 0999.05017
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.