To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
Algorithms for IVDP Matching on Short Trees |
|
Author |
G. Suganthid |
| Citation |
Vol. 9 No. 10 pp. 209-215 |
|
Abstract |
A matching in a graph is a set of edges, no two of which have a vertex in common. If edge (u,v) belongs to a matching, we say that u and v are matched to each other. One is usually interested in finding maximum matching that is, matching having a maximum number of edges. Sometimes the edges have associated weights and one is interested in finding maximum weight matchings. Problems involving matching occur in many situations. Workers may be matched to jobs, machines to parts, players to teams etc. A path matching in a graph is a set of simple paths with distinct end vertices. Two paths are said to be vertex disjoint if they don’t have any vertex in common. They are internally vertex disjoint if no vertex is an internal vertex of both the paths. A set of paths P in a graph G is said to be an internally vertex disjoint path matching(IVDP) if it is a path matching and every pair of paths in P are internally vertex disjoint. A perfect matching of G is a matching M which matches all the vertices except possibly one. This paper deals with the necessary and sufficient conditions for the existence of perfect IVDP matching for the trees of height 1 and 2. We have developed sequential and parallel algorithms and time complexity is determined. The odd and even trees are treated separately. |
|
Keywords |
Parallel Algorithms, Tree, Rooted Tree, Matching Problems, IVDP Matching |
|
URL |
