{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:33:43Z","timestamp":1752986023181},"publisher-location":"Berlin\/Heidelberg","reference-count":13,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540537090"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0020792","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T06:07:52Z","timestamp":1131862072000},"page":"118-126","source":"Crossref","is-referenced-by-count":2,"title":["Tight RNC approximations to Max Flow"],"prefix":"10.1007","author":[{"given":"Maria","family":"Serna","sequence":"first","affiliation":[]},{"given":"Paul","family":"Spirakis","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"10_CR1","unstructured":"R. J. Anderson and E. W. Mayr. Approximating P-complete problems. Technical report, Stanford University, 1986."},{"key":"10_CR2","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. A. Cook","year":"1985","unstructured":"S. A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"key":"10_CR3","volume-title":"Graph Algorithms","author":"S. Even","year":"1979","unstructured":"S. Even. Graph Algorithms. Pitman, London, 1979."},{"key":"10_CR4","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. W. H. Freeman and Co., San Francisco, 1979."},{"key":"10_CR5","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1016\/0304-3975(82)90092-5","volume":"21","author":"L. M. Goldschlager","year":"1982","unstructured":"L. M. Goldschlager, R. A. Shaw, and J. Staples. The maximum flow problem is log space complete for P. Theoretical Computer Science, 21:105\u2013111, 1982.","journal-title":"Theoretical Computer Science"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"D. B. Johnson and S. M. Venkatesan. Parallel algorithms for minimum cuts and maximum flows in planar networks. Journal of the ACM, pages 950\u2013967, 1987.","DOI":"10.1145\/31846.31849"},{"key":"10_CR7","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/BF02579264","volume":"6","author":"H. J. Karloff","year":"1986","unstructured":"H. J. Karloff. A las Vegas RNC algorithm for maximum matching. Combinatorica, 6:387\u2013392, 1986.","journal-title":"Combinatorica"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"R. M. Karp, E. Upfal, and A. Wigderson. Constructing a perfect matching is in Random NC. In 17th Annual ACM Symposium on Theory of Computing, pages 22\u201332, 1985. Also Combinatorica 6:35\u201348, 1986.","DOI":"10.1007\/BF02579407"},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"L. Kirousis, M. Serna, and P. Spirakis. The parallel complexity of the subgraph connectivity problem. In 30th Annual IEEE Symposium on Foundations of Computer Science, pages 294\u2013299, 1989.","DOI":"10.1109\/SFCS.1989.63493"},{"key":"10_CR10","unstructured":"E. L. Lawler. Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, 1976."},{"key":"10_CR11","doi-asserted-by":"crossref","unstructured":"K. Mulmuley, U. V. Vazirani, and V. V. Vazirani. Matching is as easy as matrix inversion. In 19th Annual ACM Symposium on Theory of Computing, pages 345\u2013354, 1987.","DOI":"10.1145\/28395.383347"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"M. Serna and P. Spirakis. The approximability of problems complete for P. In International Symposium on Optimal Algorithms, volume 401 of Lecture Notes in Computer Science, pages 193\u2013204. Springer-Verlag, 1989.","DOI":"10.1007\/3-540-51859-2_16"},{"key":"10_CR13","unstructured":"M. Serna and P. Spirakis. Applying P-completeness to approximation problems. Technical Report 90.05.14, CTI, Patras University, 1990. Algorithms Review to appear."}],"container-title":["Lecture Notes in Computer Science","STACS 91"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0020792.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:44:58Z","timestamp":1607550298000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0020792"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540537090"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/bfb0020792","relation":{},"subject":[]}}