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

An Optimal Parallel Matching Algorithm for Cographs

โœ Scribed by R. Lin; S. Olariu

Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
865 KB
Volume
22
Category
Article
ISSN
0743-7315

No coin nor oath required. For personal study only.

โœฆ Synopsis

The class of cographs, or complement-reducible graphs, arises naturally in many different areas of applied mathematics and computer science. We show that the problem of finding a maximum matching in a cograph can be solved optimally in parallel by reducing it to parenthesis matching. With an (n)-vertex cograph (G) represented by its parse tree as input, our algorithm finds a maximum matching in (G) in (O(\log n)) time using (O(n / \log n)) processors in the EREW-PRAM model. 01994 Academic Press, Inc.

๐Ÿ“œ SIMILAR VOLUMES

An Optimal Shortest Path Parallel Algori
An Optimal Shortest Path Parallel Algorithm for Permutation Graphs
โœ O.H. Ibarra; Q. Zheng ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 512 KB

We present an optimal parallel algorithm for the single-source shortest path problem for permutation graphs. The algorithm runs in \(O(\log n)\) time using \(O(n / \log n)\) processors on an EREW PRAM. As an application, we show that a minimum connected dominating set in a permutation graph can be f

An Efficient Parallel Algorithm for Maxi
An Efficient Parallel Algorithm for Maximum Matching for Some Classes of Graphs
โœ I. Parfenoff ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 403 KB

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, usi

Optimal Parallel Algorithms for Quadtree
Optimal Parallel Algorithms for Quadtree Problems
โœ S. Kasif ๐Ÿ“‚ Article ๐Ÿ“… 1994 ๐Ÿ› Elsevier Science โš– 449 KB

In this paper we describe optimal processor-time parallel algorithms for set operations such as union, intersection, comparison on quadtrees. The algorithms presented in this paper run in \(O(\log\) \(N\) ) time using \(N / \log N\) processors on a shared memory model of computation that allows conc