AN OPTIMAL PARALLEL MATCHING ALGORITHM FOR COGRAPHS

被引：9

作者：

LIN, R ^{[1
]}

OLARIU, S ^{[1
]}

机构：

[1] OLD DOMINION UNIV,DEPT COMP SCI,NORFOLK,VA 23529

来源：

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING | 1994年 / 22卷 / 01期

关键词：

D O I：

10.1006/jpdc.1994.1067

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 1994 Academic Press, Inc.

引用

页码：26 / 36

页数：11

共 32 条

[1] A SIMPLE PARALLEL TREE CONTRACTION ALGORITHM [J].