A Linear Time Algorithm for Deciding Interval Graph Isomorphism

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Linear Time Algorithm for Deciding Interval Graph Isomorphism

Full text

Pdf (750 KB)

Source

Journal of the ACM (JACM) archive
Volume 26 , Issue 2 (April 1979) table of contents

Pages: 183 - 195

Year of Publication: 1979

ISSN:0004-5411

Authors

George S. Lueker	Department of Information and Computer Science, University of California at Irvine, Irvine, CA
Kellogg S. Booth	Department of Computer Science, University of Waterloo, Waterloo, Ontario, Canada N2L 3G1

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 74, Citation Count: 3

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/322123.322125 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	Kellogg Speed Booth, Pq-tree algorithms., 1975
	3	BOOTH, K S Problems polynomlally equivalent to graph lsomorphtsm Tech Rep CS-77-04, Dept Comptr SCl, U of Waterloo, Waterloo, Ont, Canada, 1977
	4	BOOTH, K S, AND LUEKER, G S Testmg for the consecutive ones property, interval graphs, and graph plananty using PQ-tree algonthms J Comptr Syst Scz 13, 3 (1976), 335-379
	5	FISCHER, i, AND LADNER, R Private communlcaUon
	6	FULKERSON, D R, AND GROSS, O A Incidence matrices and interval graphs Pactfic J Math 15, 3 (1965), 835-855
	7	GAVRIL, F Algorithms for mmunum coloring, maxunum chque, minimum covering by chques, and maxtmum independent set of a chordal graph SIAM J Comptng 1, 2 (1972), 180--187
	8	GAVRIL, F The mtersectlon graphs of subtrees m trees are exactly the chordal graphs J Combmatortal Theory 16, 1 (1974), 47-56
	9	HAJ6S, G Uber eme Art von Graphen Int. Math Nachnchten 11 (1957), 65
	10	HIRSCHBERG, D, AND EDELBERG, M On the complextty of computing graph ~somorph~sm Tech Rep TR- 130, Comptr. Sci. Lab, Dept EE, Prmceton U, Princeton, N J, Aug 1973
	11	HOPCROFT, J.E., AND TARJAN, R E. Isomorphism of planar graphs In Complexity of Computer Computatwns, R E. Miller and J W Thatcher, Eds, Plenum Press, New York, 1972, pp 131-152
	12	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]
	13	KARP, R M. Reduclblhty among combmatonal problems In Complexay of Computer Computations, R E Miller and J W Thatcher, Eds., Plenum Press, New York, 1972, pp 85-104
	14	LEKKERKERKER, C.G, AND BOLAND, J CH. Representation of a finite graph by a set of mtervals on the real line Fund Math 51 (1962), 45-64
	15	LEMPEL, A, EVEN S, AND CEDERBAUM, I An algorithm for plananty testmg of graphs Proc Int Symp Theory of Graphs, Rome, July 1966, P Rosenstlehl, Ed., Gordon and Breach, New York, 1967, pp 215-232
	16	George Schick Lueker, Efficient algorithms for chordal graphs and interval graphs., 1975
	17	ROBERTS, F.S. Dzscrete Mathematwal Models, wuh Apphcatzons to Soctal, Bzologtcal and Envwonmental Problems Prentice-Hall, Englewood Chffs, N J, 1976
	18	ROSE, D J, TAR/AN, R E, AND LUEKER, G S Algorithmic aspects of vertex ellmmatton on graphs SIAM ~ Comptng 5, 2 (1976), 266-283
	19	YOUNG, S.M. Implementatton of PQ-tree algorithms Masters Th., Dept Comptr Sci, U. of Washington, Seattle, Wash, 1977

CITED BY 3

	Christoph M. Hoffmann, Testing isomorphism of cone graphs(Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.244-251, April 28-30, 1980, Los Angeles, California, United States
	Andreas Brandstädt , Feodor F. Dragan, On linear and circular structure of (claw, net)-free graphs, Discrete Applied Mathematics, v.129 n.2-3, p.285-303, 01 August 2003
	A. Vince, Graph recurrence, European Journal of Combinatorics, v.24 n.1, p.15-32, 1 January 2003