Subtree Isomorphism in O(n5/2)
Annals of discrete mathematicsPublished 1 January 1978
David W. Matula
Citations103
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
The problem of determining if the tree S (unrooted) on n, vertices is isomorphic to any subtree of the tree T on n,t≥ns vertices is shown to be solvable in O(nt3/2ns) steps. The method involves the solution of an (nt,-1) by 2(nt,-1) array of maximum bipartite matching problems where some of these subproblems are solved in groups. Recognition of isomorphic subproblems yields a compacted data structure reducing practical storage requirements with no increase in the order of time complexity.
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 ComputingAn $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
2,843 Citations1973John E. Hopcroft, Richard M. Karp
SIAM Journal on ComputingThe Planar Hamiltonian Circuit Problem is NP-Complete
517 Citations1976M. R. Garey, D. S. Johnson +1 more
The problem of determining whether a planar, cubic, triply-connected graph G has a Hamiltonian circuit is considered and it is shown that this problem is NP-complete.