MAXIMUM TREE-PACKING IN TIME O(N(5 2))

Authors
LINGAS A
Citation
A. Lingas, MAXIMUM TREE-PACKING IN TIME O(N(5 2)), Theoretical computer science, 181(2), 1997, pp. 307-316
Citations number
18
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
Journal title
Theoretical computer science → ACNP
ISSN journal
03043975
Volume
181
Issue
2
Year of publication
1997
Pages
307 - 316
Database
ISI
SICI code
0304-3975(1997)181:2<307:MTITO2>2.0.ZU;2-D
Abstract
The problem of determining the maximum number of node-disjoint subtree s of a tree T on n(t) nodes isomorphic to a tree S on n(s) nodes is sh own to be solvable in time O(n(s)(3/2)n(t)). The same asymptotic bound s are observed for the corresponding problems where topological imbedd ing and subgraph homeomorphism are respectively substituted for subgra ph isomorphism.