To obtain access to full text of journal and articles you must register!
- Article name
- IMPROVED ALGORITHM FOR TOP-DOWN MAXIMUM COMMON SUBTREE IZOMORTHISM OF TWO UNORDERED ROOTED TREES
- Authors
- Kononov D. S., , kds795@yandex.ru, ZAO "NPO "Eshelon", Moscow, Russia
- Keywords
- tree / izomorthism / common subtree / computational complexity / cost matching / bipartite graph / assignment problem / tree with attributes
- Year
- 2015 Issue 2 Pages 16 - 24
- Code EDN
- Code DOI
- Abstract
- In this article was reviewed actual results of solving maximum-cost matching in bipartite graph problem and problems, which can be brought to it, in aspect of using them in solving top-down maximum common subtree izomorthism of two unordered rooted trees problem. Several heuristics was introduced, which has allowed to reduce a number of executed operations in the algorithm for top-down maximum common subtree izomorthism of two unordered rooted trees. Estimation of computational complexity for the improved algorithm is O(N2dmax), where N - count of nodes in one tree and dmax - maximum output degree of nodes in both trees. Best previous result was O(N5/2). This received result was also generalized to trees with attributes.
- Text
- To obtain access to full text of journal and articles you must register!
- Buy
