{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T01:00:32Z","timestamp":1648515632809},"reference-count":18,"publisher":"Elsevier BV","issue":"2","license":[{"start":{"date-parts":[[1995,6,1]],"date-time":"1995-06-01T00:00:00Z","timestamp":801964800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,17]],"date-time":"2013-07-17T00:00:00Z","timestamp":1374019200000},"content-version":"vor","delay-in-days":6621,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[1995,6]]},"DOI":"10.1016\/0304-3975(94)00112-v","type":"journal-article","created":{"date-parts":[[2003,5,13]],"date-time":"2003-05-13T04:04:58Z","timestamp":1052798698000},"page":"309-318","source":"Crossref","is-referenced-by-count":1,"title":["The maximal f-dependent set problem for planar graphs is in NC"],"prefix":"10.1016","volume":"143","author":[{"given":"Zhi-Zhong","family":"Chen","sequence":"first","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/0304-3975(94)00112-V_BIB1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","article-title":"A fast and simple randomized parallel algorithm for the maximal independent set problem","volume":"7","author":"Alon","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(94)00112-V_BIB2","series-title":"Graph Theory with Applications","author":"Bondy","year":"1980"},{"key":"10.1016\/0304-3975(94)00112-V_BIB3","unstructured":"Z.-Z. Chen and X. He, Parallel algorithms for maximal cycle-free sets, submitted for publication."},{"key":"10.1016\/0304-3975(94)00112-V_BIB4","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/0196-6774(89)90022-9","article-title":"Fast algorithms for edge-coloring planar graphs","volume":"10","author":"Chrobak","year":"1986","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(94)00112-V_BIB5","series-title":"Proc. 2nd Internat. Symp. on Algorithms","first-page":"385","article-title":"Parallel algorithm for finding maximal k-dependent sets and maximalf-matchings","volume":"Vol. 557","author":"Diks","year":"1991"},{"key":"10.1016\/0304-3975(94)00112-V_BIB6","series-title":"Efficient Parallel Algorithms","author":"Gibbons","year":"1988"},{"key":"10.1016\/0304-3975(94)00112-V_BIB7","series-title":"Proc. 19th ACM Symp. on Theory of Computing","first-page":"315","article-title":"Parallel symmetry-breaking in sparse graphs","author":"Goldberg","year":"1987"},{"key":"10.1016\/0304-3975(94)00112-V_BIB8","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1137\/0218029","article-title":"A new parallel algorithm for the maximal independent set problem","volume":"18","author":"Goldberg","year":"1989","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)00112-V_BIB9","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1137\/0402028","article-title":"Constructing a maximal independent set in parallel","volume":"2","author":"Goldberg","year":"1989","journal-title":"SIAM J. Discrete Math."},{"key":"10.1016\/0304-3975(94)00112-V_BIB10","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1016\/0020-0190(86)90144-4","article-title":"A fast and simple randomized parallel algorithm for maximal matching","volume":"22","author":"Israeli","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00112-V_BIB11","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0020-0190(86)90141-9","article-title":"An improved maximal matching parallel algorithm","volume":"22","author":"Israeli","year":"1986","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/0304-3975(94)00112-V_BIB12","first-page":"868","article-title":"Parallel algorithms for shared memory machines","volume":"Vol. A","author":"Karp","year":"1990"},{"key":"10.1016\/0304-3975(94)00112-V_BIB13","doi-asserted-by":"crossref","first-page":"762","DOI":"10.1145\/4221.4226","article-title":"A fast parallel algorithm for the maximal independent set problem","volume":"32","author":"Karp","year":"1985","journal-title":"J. ACM"},{"key":"10.1016\/0304-3975(94)00112-V_BIB14","article-title":"Matching Theory","author":"Lov\u00e1sz","year":"1986"},{"key":"10.1016\/0304-3975(94)00112-V_BIB15","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","article-title":"A simple parallel algorithm for the maximal independent set problem","volume":"15","author":"Luby","year":"1986","journal-title":"SIAM J. Comput."},{"key":"10.1016\/0304-3975(94)00112-V_BIB16","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1006\/jagm.1993.1008","article-title":"Efficient sequential and parallel algorithms for maximal bipartite sets","volume":"14","author":"Pearson","year":"1993","journal-title":"J. Algorithms"},{"key":"10.1016\/0304-3975(94)00112-V_BIB17","series-title":"Proc. 17th International Workshop on Graph-Thoeretic Concepts in Computer Science","first-page":"126","article-title":"Using maximal independent sets to solve problems in parallel","volume":"Vol. 570","author":"Shoudai","year":"1991"},{"key":"10.1016\/0304-3975(94)00112-V_BIB18","series-title":"Proc. 7th IBM Symp. on Mathematical Foundations of Computer Science","first-page":"173","article-title":"Parallel Computation","author":"Valiant","year":"1982"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400112V?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:030439759400112V?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,4,26]],"date-time":"2019-04-26T05:26:43Z","timestamp":1556256403000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/030439759400112V"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,6]]}},"alternative-id":["030439759400112V"],"URL":"https:\/\/doi.org\/10.1016\/0304-3975(94)00112-v","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[1995,6]]}}}