๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Parallel computation of matchings in trees

โœ Scribed by Constantine N.K. Osiakwan; Selim G. Akl

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
932 KB
Volume
17
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

โœฆ Synopsis

We present adaptive parallel algorithms for b-matchings in trees. The algorithms are designed using the exclusive-read exclusive-write parallel random-access machine (EREW PRAM) model of parallel computation. For a tree of n vertices, we present an algorithm that determines a maximum cardinality b-matching in O(n/p +log n) time using p processors, where p ~< n. An algorithm that executes in O(n/p' +log n) time, where 1 < np/(n + p log n) ~< p' < p -N< n and p > 1/n-/log n is also designed for the maximum weight b-matching problem in trees. When p ~< n/(log n), the algorithm are cost-optimal.

๐Ÿ“œ SIMILAR VOLUMES

Parallel tree pattern matching
Parallel tree pattern matching
โœ R. Ramesh; I.V. Ramakrishnan ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 819 KB

Tree pattern matching is a fundamental operation that is used in a number of programming tasks such as code optimization in compilers, symbolic computation, automatic theorem proving and term rewriting. An important special case of this operation is linear tree pattern matching in which an instance

Matchings in starlike trees
Matchings in starlike trees
โœ I. Gutman; O. Araujo; J. Rada ๐Ÿ“‚ Article ๐Ÿ“… 2001 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 250 KB

## Let m(G,k) be the number of k-matchings in the graph G. We write G1 -~ G2 if m(Gl,k) <\_ m(G2,k) for all k = 1,2,.... A tree is said to be starlike if it possesses exactly one vertex of degree greater than two. The relation T1 -~ T2 is shown to hold for various pairs of starlike trees T1,T2. T

A parallel algorithm for tree pattern ma
A parallel algorithm for tree pattern matching
โœ Koji Tarora; Tomio Hirata; Yasuyoshi Inagaki ๐Ÿ“‚ Article ๐Ÿ“… 1993 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 814 KB

## Abstract Given a text tree __t__ and a pattern tree __p__, tree pattern matching involves finding subtrees of __t__ which match __p.__ This paper proposed a parallel algorithm for tree pattern matching. The algorithm is designed to run in __O__(log __n__) parallel time using __mn__/log__n__ proc