{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,27]],"date-time":"2026-06-27T15:01:04Z","timestamp":1782572464276,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":14,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540594086","type":"print"},{"value":"9783540492450","type":"electronic"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59408-6_38","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:15:22Z","timestamp":1330276522000},"page":"14-28","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":23,"title":["Approximating minimum feedback sets and multi-cuts in directed graphs"],"prefix":"10.1007","author":[{"given":"Guy","family":"Even","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Schieber","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Madhu","family":"Sudan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"2_CR1","volume-title":"Digital Systems Testing and Testable Design","author":"M. Abramovici","year":"1990","unstructured":"M. Abramovici, M.A. Breuer and A.D. Friedman, \u201cDigital Systems Testing and Testable Design,\u201d New York, Computer Science Press, 1990."},{"key":"2_CR2","doi-asserted-by":"crossref","unstructured":"N. Garg, V.V. Vazirani and M. Yannakakis, \u201cApproximate max-flow min-(multi) cut theorems and their applications,\u201d 25th STOC, pp. 698\u2013707, 1993.","DOI":"10.1145\/167088.167266"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"R. Gupta, R. Gupta and M.A. Breuer, \u201cBALLAST: A Methodology for Partial Scan Design,\u201d Proc. 19th Int'l. Symp. on Fault-Tolerant Computing,' pp. 118\u2013125, June, 1989.","DOI":"10.1109\/FTCS.1989.105553"},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1287\/opre.11.3.344","volume":"11","author":"T.C. Hu","year":"1963","unstructured":"T.C. Hu, \u201cMulti-commodity network flows,\u201d Operations Research, 11, pp. 344\u2013360, 1963.","journal-title":"Operations Research"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R.M. Karp","year":"1972","unstructured":"R.M. Karp, \u201cReducibility among combinatorial problems,\u201d Complexity of Computer Computations, pp. 85\u2013104, Plenum Press, N.Y., 1972."},{"key":"2_CR6","unstructured":"P.N. Klein, S.A. Plotkin, S. Rap and \u00c9. Tardos, \u201cNew network decompositions theorems with applications,\u201d unpublished manuscript, 1993."},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"P. Klein, A. Agrawal, R. Ravi, and S. Rao, \u201cApproximation through multi-commodity flow,\u201d 31st FOCS, pp. 726\u2013737, 1990.","DOI":"10.1109\/FSCS.1990.89595"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"P. Klein, C. Stein, and \u00c9. Tardos, \u201cLeighton-Rao might be practical: faster approximation algorithms for concurrent flow with uniform capacities,\u201d 22nd STOC, pp. 310\u2013321, 1990.","DOI":"10.1145\/100216.100257"},{"key":"2_CR9","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF00137392","volume":"1","author":"A. Kunzmann","year":"1990","unstructured":"A. Kunzmann and H.J. Wunderlich, \u201cAn Analytical Approach to the Partial Scan Problem,\u201d Journal of Elec. Testing: Theory and Applications, 1, pp. 163\u2013174, 1990.","journal-title":"Journal of Elec. Testing: Theory and Applications"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"M. Luby and N. Nisan, \u201cA parallel approximation algorithm for positive linear programming,\u201d 25th STOC, pp. 448-457, 1993.","DOI":"10.1145\/167088.167211"},{"key":"2_CR11","doi-asserted-by":"crossref","unstructured":"T. Leighton and S. Rao, \u201cAn approximate max-flow min-cut theorem for uniform multi-commodity flow problems with applications to approximation algorithms,\u201d 29th FOCS, pp. 422\u2013431, 1988. Directed graphs are dealt with in manuscript, Feb., 1992.","DOI":"10.1109\/SFCS.1988.21958"},{"issue":"No.1","key":"2_CR12","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1007\/BF01759032","volume":"6","author":"C.E. Leiserson","year":"1991","unstructured":"C.E. Leiserson and J.B. Saxe, \u201cRetiming Synchronous Circuitry,\u201d Algorithmica, Vol. 6, No. 1, pp. 5\u201335. 1991.","journal-title":"Algorithmica"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"S. Plotkin, \u00c9. Tardos and D. Shmoys, \u201cFast approximation algorithms for fractional packing and covering problems\u201d, 32nd FOCS, pp. 495\u2013504, 1991.","DOI":"10.1109\/SFCS.1991.185411"},{"key":"2_CR14","unstructured":"P.D. Seymour, \u201cPacking Directed Circuits Fractionally,\u201d Manuscript, (1992). To appear in Combinatorica."}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59408-6_38","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:45:57Z","timestamp":1742597157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59408-6_38"}},"subtitle":["Extended summary"],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540594086","9783540492450"],"references-count":14,"URL":"https:\/\/doi.org\/10.1007\/3-540-59408-6_38","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"1 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}