𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs

✍ Scribed by I. Parfenoff

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
403 KB
Volume
52
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

✦ Synopsis

The P 4 -tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P 4 (cographs, P 4 -sparse graphs, P 4 -lite graphs). Here, we propose an extension of R. Lin and S. Olariu's work (1994. J. Parallel Distributed Computing 22, 26 36.) on cographs, using the modular decomposition. As an application, we show how to obtain a maximum matching parallel algorithm for the family of P 4 -tidy graphs (represented by a parse tree) in O(log n) time with O(nΓ‚log n) processors in the EREW-PRAM model with n-vertex graphs.

πŸ“œ SIMILAR VOLUMES

Efficient Parallel Algorithms for Graphs
Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
✍ Jens Lagergren πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 236 KB

We present an efficient parallel algorithm for the tree-decomposition problem Ε½ 3 . Ε½. for fixed width w. The algorithm runs in time O O log n and uses O O n processors on an ARBITRARY CRCW PRAM. The sequential complexity of our tree-decom-Ε½ 2 . position algorithm is O O n log n . The tree-decomposi

An Optimal Simple Parallel Algorithm for
An Optimal Simple Parallel Algorithm for Testing Isomorphism of Maximal Outerplanar Graphs
✍ Shan-Chyun Ku; Biing-Feng Wang πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 91 KB

An outerplanar graph is a planar graph that can be imbedded in the plane in such a way that all vertices lie on the exterior face. An outerplanar graph is maximal if no edge can be added to the graph without violating the outerplanarity. In this paper, an optimal parallel algorithm is proposed on th

An efficient parallel algorithm for the
An efficient parallel algorithm for the calculation of canonical MP2 energies
✍ Jon Baker; Peter Pulay πŸ“‚ Article πŸ“… 2002 πŸ› John Wiley and Sons 🌐 English βš– 111 KB

## Abstract We present the parallel version of a previous serial algorithm for the efficient calculation of canonical MP2 energies (Pulay, P.; Saebo, S.; Wolinski, K. Chem Phys Lett 2001, 344, 543). It is based on the Saebo–AlmlΓΆf direct‐integral transformation, coupled with an efficient prescreeni

An efficient parallel algorithm for thre
An efficient parallel algorithm for three-dimensional analysis of subsidence above gas reservoirs
✍ B.A. Schrefler; X. Wang; V.A. Salomoni; G. Zuccolo πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 254 KB

In this paper an efficient parallel algorithm to solve a three-dimensional problem of subsidence above exploited gas reservoirs is presented. The parallel program is developed on a cluster of workstations. The parallel virtual machine (PVM) system is used to handle communications among networked wor