Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear Algorithms for Isomorphism of Maximal Outerplanar Graphs

Full text

Pdf (420 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 4 (October 1979) table of contents

Pages: 603 - 610

Year of Publication: 1979

ISSN:0004-5411

Authors

S. Mitchell	Department of Computer Science, University of Oregon, Eugene, OR and University of Louisville, Louisville, Kentucky
T. Beyer	The Computer Center, University of Oregon, Eugene, OR
W. Jones	Department of Applied Mathematics and Computer Science, University of Louisville, Louisville, KY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 31, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/322154.322155 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BINEKE, L, AND PIPPERT, R A census of ball and disk dlssecUons In Proc of the Graph Theory Conf. at Western Mchlgan UmversJty, 1972, Y. Alavl, D. Lick, and A White, Eds., Spnnger Lecture Notes m Math #303, Spnnger-Verlag, Heidelberg, 1974, pp 25-40
	3	BOOTH, K, AND LUEKER, G Linear algorithms to recogmze interval graphs and test for the consecutwe ones property. J Comptr. Syst Sct 13 (1976), 335-379
	4	D. G. Corneil , C. C. Gotlieb, An Efficient Algorithm for Graph Isomorphism, Journal of the ACM (JACM), v.17 n.1, p.51-64, Jan. 1970 [doi>10.1145/321556.321562]
	5	GAVRIL, F Algorithms for minunum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph SIAM J. Comptng 1 (1972), 180-187.
	6	GOODMAN, S, HEDETNIEMI, S., AND TARJAN, R. B-matchmgs m trees SIAM Z Comping..5 (1976), 104-108.
	7	HARARY, F. Graph Theory Addison-Wesley, Reading, Mass., 1969.
	8	HEDETNIEMI, S, CitARTRAND, G , AND GELLER, D Graphs with forbidden suhgraphs. J. Combinatorial Theory 10 (1971) 12-41.
	9	HOPCROFT, J , AND TRJAN, R Isomorphism of planar graphs In Complexity ofComputanons, R. Miller and J, Thatcher, Eds., Plenum Press, New York, 1972, pp. 143-150.
	10	J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
	11	JORDAN, C. Sur les assemblages de hgnes. J Reme Angem Math. 70 (1869), 185-190.
	12	KERSHENBAUM, A., AND VAN SLYKE, R Recursive analysts of network reliability Networks 3 (1973), 81-94
	13	MISHRA, J , AND TARJAN, R Optimal chain partitions of trees Information Processing Letters 4 (1975), 24- 26
	14	Sandra Lee Mitchell, Algorithms on trees and maximal outerplanar graphs: design, complexity analysis, and data structures study., 1977
	15	MITCHELL, S , COCKAYNE, E , AND HEDETNIEMI, S Linear algorithms on recurslve representations of trees. J Comptr Syst Scl 18(1979), 76-85
	16	MORRIS, J. H JR,, AND PRATT, V R A linear pattern matching algorithm Tech Rep No 40, Computing Center, U. of California, Berkeley, Calif., 1970.
	17	READ, R, AND CORNEIL, D The graph isomorphism disease J Graph Theory I (1977), 239-363
	18	ROSE, D On single characterizations of K-trees D:serete Math 7 (1974), 317-322
	19	WEINBERG, L A simple and efficient algorithm for determining isomorphism of planar triply connected graphs. IEEE Trans Circuit Theory CT.13 (1966), 142-148

CITED BY 5

	Stefan Arnborg , Bruno Courcelle , Andrzej Proskurowski , Detlef Seese, An algebraic theory of graph reduction, Journal of the ACM (JACM), v.40 n.5, p.1134-1164, Nov. 1993
	Shan-Chyun Ku , Biing-Feng Wang, An optimal simple parallel algorithm for testing isomorphism of maximal outerplanar graphs, Journal of Parallel and Distributed Computing, v.62 n.2, p.221-227, February 2002
	Ali A. Kooshesh , Bernard M. E. Moret, Folding a simple polygon: a paradigm for computational geometry, Proceedings of the 1995 ACM 23rd annual conference on Computer science, p.114-118, February 28-March 02, 1995, Nashville, Tennessee, United States
	L. Markenzon , C. M. Justel , N. Paciornik, Subclasses of k-trees: characterization and recognition, Discrete Applied Mathematics, v.154 n.5, p.818-825, 1 April 2006
	Timo Poranen, Two new approximation algorithms for the maximum planar subgraph problem, Acta Cybernetica, v.18 n.3, p.503-527, January 2008