咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >Parallel maximum independent s... 收藏

Parallel maximum independent set in convex bipartite graphs

平行最大的独立人士在凸的由两部组成的图设定

作     者:Czumaj, A Diks, K Przytycka, TM 

作者机构: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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分