George S. Lueker
Kellogg S. Booth
- 1 AHO, A V, HOPCROFT, J E, AND ULLMAN, J D The Design and Analysts of Computer Algorithms Addtson- Wesley, Reading, Mass, 1974. 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 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, 1977Google 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-379Google Scholar
- 5 FISCHER, i, AND LADNER, R Private communlcaUonGoogle Scholar
- 6 FULKERSON, D R, AND GROSS, O A Incidence matrices and interval graphs Pactfic J Math 15, 3 (1965), 835-855Google 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--187Google Scholar
- 8 GAVRIL, F The mtersectlon graphs of subtrees m trees are exactly the chordal graphs J Combmatortal Theory 16, 1 (1974), 47-56Google Scholar
- 9 HAJ6S, G Uber eme Art von Graphen Int. Math Nachnchten 11 (1957), 65Google 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 1973Google 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-152Google 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 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-104Google 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-64Google 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-232Google 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 Google Scholar
- 17 ROBERTS, F.S. Dzscrete Mathematwal Models, wuh Apphcatzons to Soctal, Bzologtcal and Envwonmental Problems Prentice-Hall, Englewood Chffs, N J, 1976Google 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-283Google Scholar
- 19 YOUNG, S.M. Implementatton of PQ-tree algorithms Masters Th., Dept Comptr Sci, U. of Washington, Seattle, Wash, 1977Google Scholar
Index Terms
- A Linear Time Algorithm for Deciding Interval Graph Isomorphism
Recommendations
Linear time algorithm for isomorphism of planar graphs (Preliminary Report)
STOC '74: Proceedings of the sixth annual ACM symposium on Theory of computingThe isomorphism problem for graphs G1 and G2 is to determine if there exists a one-to-one mapping of the vertices of G1 onto the vertices of G2 such that two vertices of G1 are adjacent if and only if their images in G2 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