{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T19:01:25Z","timestamp":1649098885505},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1993,6]]},"abstract":"<jats:p> Let k be a positive integer, a subset Q of the set of vertices of a graph G is k-dependent in G if each vertex of Q has no more than k neighbours in Q. We present a parallel algorithm which computes a maximal k-dependent set in a graph on n nodes in time O( log <jats:sup>4<\/jats:sup> n) on an EREW PRAM with O(n<jats:sup>2<\/jats:sup>) processors. In this way, we establish the membership of the problem of constructing a maximal k-dependent set in the class NC. Our algorithm can be easily adapted to compute a maximal k-dependent set in a graph of bounded valence in time O( log * n) using only O(n) EREW PRAM processors. Let f be a positive integer function defined on the set V of vertices of a graph G. A subset F of the set of edges of G is said to be an f-matching if every vertex v\u025bV is adjacent to at most f(v) edges in-F. We present the first NC algorithm for constructing a maximal f-matching. For a graph on n nodes and m edges the algorithm runs in time O( log <jats:sup>4<\/jats:sup> n) and uses O(n+m) EREW PRAM processors. For graphs of constantly bounded valence, we can construct a maximal f-matching in O( log * n) time on an EREW PRAM with O(n) processors. <\/jats:p>","DOI":"10.1142\/s0129054193000122","type":"journal-article","created":{"date-parts":[[2004,11,23]],"date-time":"2004-11-23T03:29:30Z","timestamp":1101180570000},"page":"179-192","source":"Crossref","is-referenced-by-count":4,"title":["PARALLEL ALGORITHMS FOR FINDING MAXIMAL k-DEPENDENT SETS AND MAXIMAL f-MATCHINGS"],"prefix":"10.1142","volume":"04","author":[{"given":"KRZYSZTOF","family":"DIKS","sequence":"first","affiliation":[{"name":"Institute of Informatics, Warsaw University, ul. Banacha 2 02\u2013097 Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"OSCAR","family":"GARRIDO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118 S-221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ANDRZEJ","family":"LINGAS","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Lund University, Box 118 S-221 00 Lund, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054193000122","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:55:08Z","timestamp":1565139308000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054193000122"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,6]]},"references-count":0,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1993,6]]}},"alternative-id":["10.1142\/S0129054193000122"],"URL":"https:\/\/doi.org\/10.1142\/s0129054193000122","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,6]]}}}