版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:UNIV PADERBORNDEPT MATH & COMP SCID-33095 PADERBORNGERMANY UNIV WARSAWINST INFORMATPL-02097 WARSAWPOLAND UNIV MARYLANDDEPT COMP SCICOLLEGE PKMD 20742
出 版 物:《INFORMATION PROCESSING LETTERS》 (信息处理快报)
年 卷 期:1996年第59卷第6期
页 面:289-294页
核心收录:
学科分类:08[工学] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:DFG-Graduiertenkolleg EC Cooperative Action K-1000
主 题:bipartite graphs convex graphs independent set PRAM algorithms
摘 要:A bipartite graph G = (V, W, E) is called convex if the vertices in W can be ordered in such a way that the elements of W adjacent to any vertex nu is an element of V form an interval (i.e. a sequence consecutively numbered vertices). Such a graph can be represented in a compact form that requires O(n) space, where n = max{\V\, \W\}. Given a convex bipartite graph G in the compact form Dekel and Sahni designed an O(log(2)(n))-time, n-processor EREW PRAM algorithm to compute a maximum matching in G, We show that the matching produced by their algorithm can be used to construct optimally in parallel a maximum set of independent vertices. Our algorithm runs in O(log n) time with nl log n processors on an Arbitrary CRCW PRAM.