article

Free access

A Linear Time Algorithm for Deciding Interval Graph Isomorphism

Authors:

George S. Lueker,

Kellogg S. BoothAuthors Info & Claims

Journal of the ACM (JACM), Volume 26, Issue 2

Pages 183 - 195

https://doi.org/10.1145/322123.322125

Published: 01 April 1979 Publication History

PDF eReader

References

[1]

AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms Addtson- Wesley, Reading, Mass, 1974.

Crossref

Google Scholar

[2]

BOOTH, K S PQ-tree algorithms Ph D. Dlss, Dept EECS, U of Cahfornla, Berkeley, Cahf, 1975, also UCRL-51953, Lawrence Llvermore Lab, Llvermore, Cahf, 1975

Crossref

Google Scholar

[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

Google Scholar

[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

Google Scholar

[5]

FISCHER, i, AND LADNER, R Private communlcaUon

Google Scholar

[6]

FULKERSON, D R, AND GROSS, O A Incidence matrices and interval graphs Pactfic J Math 15, 3 (1965), 835-855

Google Scholar

[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

Google Scholar

[8]

GAVRIL, F The mtersectlon graphs of subtrees m trees are exactly the chordal graphs J Combmatortal Theory 16, 1 (1974), 47-56

Google Scholar

[9]

HAJ6S, G Uber eme Art von Graphen Int. Math Nachnchten 11 (1957), 65

Google Scholar

[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

Google Scholar

[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

Google Scholar

[12]

HOPCROFT, J E., AND WONG, J.K Linear tune algorithm for isomorphism of planar graphs Proc 6th Annual ACM Symp. Theory of Comptng, 1974, pp 172-184

Crossref

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[16]

LUEKER, G.S. Efficient algorithms for chordal graphs and interval graphs Ph D. Dtss., Prog Appl Math and Dept. EE, Princeton U, Princeton, N J, 1975

Crossref

Google Scholar

[17]

ROBERTS, F.S. Dzscrete Mathematwal Models, wuh Apphcatzons to Soctal, Bzologtcal and Envwonmental Problems Prentice-Hall, Englewood Chffs, N J, 1976

Google Scholar

[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

Google Scholar

[19]

YOUNG, S.M. Implementatton of PQ-tree algorithms Masters Th., Dept Comptr Sci, U. of Washington, Seattle, Wash, 1977

Google Scholar

Cited By

View all

Dallard CGanian RHatzel MKrnc MMilanič M(2024)Graphs with at most two moplexesJournal of Graph Theory10.1002/jgt.23102107:1(38-69)Online publication date: 8-May-2024
https://doi.org/10.1002/jgt.23102
Galby EMarx DSchepper PSharma RTale P(2023)Parameterized complexity of multicut in weighted treesTheoretical Computer Science10.1016/j.tcs.2023.114174978(114174)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114174
Li KLi JSun YLi CWang C(2023)Color assignment optimization for categorical data visualization with adjacent blocksJournal of Visualization10.1007/s12650-022-00905-z26:4(917-936)Online publication date: 6-Jan-2023
https://dl.acm.org/doi/10.1007/s12650-022-00905-z
Show More Cited By

Index Terms

A Linear Time Algorithm for Deciding Interval Graph Isomorphism
1. Mathematics of computing
  1. Discrete mathematics
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Linear time algorithm for isomorphism of planar graphs (Preliminary Report)
STOC '74: Proceedings of the sixth annual ACM symposium on Theory of computing

The isomorphism problem for graphs G₁ and G₂ is to determine if there exists a one-to-one mapping of the vertices of G₁ onto the vertices of G₂ such that two vertices of G₁ are adjacent if and only if their images in G₂ are adjacent. In addition to ...
A linear time algorithm for liar's domination problem in proper interval graphs

Let G=(V,E) be a graph without isolated vertices and having at least 3 vertices. A set L@?V(G) is a liar@?s dominating set if (1) |N"G[v]@?L|>=2 for all v@?V(G), and (2) |(N"G[u]@?N"G[v])@?L|>=3 for every pair u,v@?V(G) of distinct vertices in G, where ...
Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs

Given two graphs G and H as input, the Induced Subgraph Isomorphism (ISI) problem is to decide whether G has an induced subgraph that is isomorphic to H. This problem is NP-complete already when G and H are restricted to disjoint unions of paths, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 26, Issue 2

April 1979

205 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322123

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1979

Published in JACM Volume 26, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

142
Total Citations
View Citations
1,662
Total Downloads

Downloads (Last 12 months)136
Downloads (Last 6 weeks)18

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Dallard CGanian RHatzel MKrnc MMilanič M(2024)Graphs with at most two moplexesJournal of Graph Theory10.1002/jgt.23102107:1(38-69)Online publication date: 8-May-2024
https://doi.org/10.1002/jgt.23102
Galby EMarx DSchepper PSharma RTale P(2023)Parameterized complexity of multicut in weighted treesTheoretical Computer Science10.1016/j.tcs.2023.114174978(114174)Online publication date: Nov-2023
https://doi.org/10.1016/j.tcs.2023.114174
Li KLi JSun YLi CWang C(2023)Color assignment optimization for categorical data visualization with adjacent blocksJournal of Visualization10.1007/s12650-022-00905-z26:4(917-936)Online publication date: 6-Jan-2023
https://dl.acm.org/doi/10.1007/s12650-022-00905-z
Galby EMarx DSchepper PSharma RTale P(2023)Domination and Cut Problems on Chordal Graphs with Bounded LeafageAlgorithmica10.1007/s00453-023-01196-y86:5(1428-1474)Online publication date: 29-Dec-2023
https://doi.org/10.1007/s00453-023-01196-y
TAKAOKA A(2022)Simple-Triangle Graphs and Related ClassesSimple-Triangle Graphとその周辺IEICE ESS Fundamentals Review10.1587/essfr.16.1_1716:1(17-23)Online publication date: 1-Jul-2022
https://doi.org/10.1587/essfr.16.1_17
Şeker OHeggernes PEkim TTaşkın Z(2022)Generation of random chordal graphs using subtrees of a treeRAIRO - Operations Research10.1051/ro/202202756:2(565-582)Online publication date: 25-Mar-2022
https://doi.org/10.1051/ro/2022027
de Figueiredo Cde Melo ASasaki DSilva A(2022)Revising Johnson’s table for the 21st centuryDiscrete Applied Mathematics10.1016/j.dam.2021.05.021323:C(184-200)Online publication date: 31-Dec-2022
https://dl.acm.org/doi/10.1016/j.dam.2021.05.021
Gutowski GMittelstädt FRutter ISpoerhase JWolff AZink J(2022)Coloring Mixed and Directional Interval GraphsGraph Drawing and Network Visualization10.1007/978-3-031-22203-0_30(418-431)Online publication date: 13-Sep-2022
https://dl.acm.org/doi/10.1007/978-3-031-22203-0_30
Arvind VNedela RPonomarenko IZeman P(2022)Testing Isomorphism of Chordal Graphs of Bounded Leafage is Fixed-Parameter Tractable (Extended Abstract)Graph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_3(29-42)Online publication date: 22-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-15914-5_3
Klavík PKnop DZeman P(2021)Graph isomorphism restricted by listsTheoretical Computer Science10.1016/j.tcs.2021.01.027Online publication date: Jan-2021
https://doi.org/10.1016/j.tcs.2021.01.027
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

Linear time algorithm for isomorphism of planar graphs (Preliminary Report)

A linear time algorithm for liar's domination problem in proper interval graphs

Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations