A-Z
- A
- B
- C
- D
- E
- F
- G
- H
- I
- J
- K
- L
- M
- N
- O
- P
- Q
- R
- S
- T
- U
- V
- W
- X
- Y
- Z
- 0-9
Classification
Publication

- Full text
- Title
- Author
- ISBN/ISSN
- Publisher
AdvancedSearch
- AdvancedSearch
- Search help

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

Author： Parfenoff I.

Publisher： Academic Press

ISSN： 0743-7315

Source： Journal of Parallel and Distributed Computing, Vol.52, Iss.1, 1998-07, pp. : 96-108

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

The P₄-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with few induced P₄(cographs,P₄-sparse graphs, P₄-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₄-tidy graphs (repre- sented by a parse tree) in O(log n) time with O(n/log n) processors in the EREW-PRAM model with n-vertex graphs. Copyright 1998 Academic Press.

Related content

Efficient Scheduling of Arbitrary Task Graphs to Multiprocessors Using a Parallel Genetic Algorithm

By Kwok Y-K. Ahmad I.

Journal of Parallel and Distributed Computing, Vol. 47, Iss. 1, 1997-11 ,pp. : 58-77 (20)

Access to resources Recommend Favorite

A sublinear parallel algorithm for stable matching

By Feder T. Megiddo N. Plotkin S.A.

Theoretical Computer Science, Vol. 233, Iss. 1, 2000-02 ,pp. : 297-308 (12)

Access to resources Recommend Favorite

The greedy algorithm for domination in graphs of maximum degree 3

Information Processing Letters, Vol. 89, Iss. 2, 2004-01 ,pp. : 53-56 (4)

Access to resources Recommend Favorite

Efficient parallel algorithms for doubly convex-bipartite graphs

By Chang-Wu Y. Gen-Huey C.

Theoretical Computer Science, Vol. 147, Iss. 1, 1995-08 ,pp. : 249-265 (17)

Access to resources Recommend Favorite

A New Efficient Block-Matching Algorithm for Motion Estimation

By Mahmoud Hanan Goel Sumeer Shaaban Mohsen Bayoumi Magdy

Journal of VLSI Signal Processing, Vol. 42, Iss. 1, 2006-01 ,pp. : 21-33 (13)

Springer Publishing Company

Access to resources Recommend Favorite