Subgraph isomorphism for biconnected outerplanar graphs in cubic time
Theoretical Computer SciencePublished 1 March 1989
Andrzej Lingas
Citations56
SJR quartileQ2
SJR score0.49
SNIP0.94
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
A dynamic programming algorithm for determining whether a biconnected outerplanar graph is isomorphic to a subgraph of another biconnected outerplanar graph is presented. The algorithm runs in cubic time.
Keywords
Computer Science
The Design and Analysis of Computer Algorithms
9,456 Citations1974Alfred V. Aho, John E. Hopcroft
This text introduces the basic data structures and programming techniques often used in efficient algorithms, and covers use of lists, push-down stacks, queues, trees, and graphs.
SIAM Journal on ComputingApplications of a Planar Separator Theorem
640 Citations1980Richard J. Lipton, Robert E. Tarjan
Isomorphism testing for graphs of bounded genus
147 Citations1980Gary L. Miller
This result is noteworthy for at least two reasons: first, it extends the polynomial time isomorphism results for the plane [HT 72] and also the projective plane [L 80] to arbitrary surfaces and secondly it gives one of the few known natural decompositions of the isomorphicism problem into an infinite hierarchy of problems.
Information Processing LettersLinear algorithms to recognize outerplanar and maximal outerplanar graphs
122 Citations1979S. Mitchell
This paper presents conceptually simpler algorithms to determine if a graph is a maximal outerplanar orouterplanar graph, and restricts the discussion to biconnected graphs.
SIAM Journal on ComputingAn Analysis of a Good Algorithm for the Subtree Problem
108 Citations1977Steven W. Reyner
A good algorithm is analyzed for deciding if one tree is a subtree of another tree, and the total number of computations is $O(nm^{1.5})$ or better, depending on how good an algorithm one has for a maximal matching in a bipartite graph.
SIAM Journal on ComputingThe Pebbling Problem is Complete in Polynomial Space
81 Citations1980John R. Gilbert, Thomas Lengauer +1 more
Isomorphism of graphs of bounded valence can be tested in polynomial time
76 Citations1980Eugene M. Luks
Testing isomorphism of graphs of valence ≤ t is polynomial-time reducible to the color automorphism problem for groups with small simple sections, and some results on primitive permutation groups are used to show that the algorithm runs inPolynomial time.
Theoretical Computer ScienceThe subgraph isomorphism problem for outerplanar graphs
64 Citations1982Maciej M. SysŁ o
It is shown that SUBOUTISOM remains NP-complete even when the strongest connectivity requirements are imposed on both graphs, except the case when both graphs arc 2-connected.