{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:54:16Z","timestamp":1725551656047},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540638902"},{"type":"electronic","value":"9783540696629"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63890-3_36","type":"book-chapter","created":{"date-parts":[[2010,4,5]],"date-time":"2010-04-05T17:12:11Z","timestamp":1270487531000},"page":"334-343","source":"Crossref","is-referenced-by-count":0,"title":["On defect sets in bipartite graphs (extended abstract)"],"prefix":"10.1007","author":[{"given":"P. E.","family":"Haxell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M.","family":"Loebl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,7,29]]},"reference":[{"key":"36_CR1","unstructured":"A. Aggarwal, A. Bar-noy, D. Coppersmith, R. Ramaswami, B. Schieber, M. Sudan, Efficient Routing and Scheduling Algorithms for Optical Networks, in Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, Pennsylvania, 23\u201325 January 1994, pp. 412\u2013423."},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"M. Ajtai, Generating Hard Instances of Lattice Problems, preprint 1996.","DOI":"10.1145\/237814.237838"},{"key":"36_CR3","unstructured":"I. Barany, S. Onn, Colourful Linear Programming And its Relatives, Mathematics of Operations Research, to appear."},{"key":"36_CR4","doi-asserted-by":"crossref","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E.R. Berlekamp","year":"1978","unstructured":"E.R. Berlekamp, R. McEliece, H. van Tilborg, On the Inherent Intractability of Certain Coding Problems, IEEE Transactions on Information Theory 24 (1978), pp.384\u2013386.","journal-title":"IEEE Transactions on Information Theory"},{"key":"36_CR5","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1016\/0020-0190(81)90050-8","volume":"13","author":"M. Blum","year":"1981","unstructured":"M. Blum, R.M. Karp, O. Vornberger, C.H. Papadimitriou, M. Yannakakis, The Complexity of Testing Whether a Graph Is a Superconcentrator, Information Processing Letters 13 (1981), pp. 164\u2013167.","journal-title":"Information Processing Letters"},{"key":"36_CR6","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1137\/0401018","volume":"1","author":"P. Feldman","year":"1988","unstructured":"P. Feldman, J. Friedman, N. Pippenger, Wide-Sense Nonblocking Networks, SIAM J. Disc. Math. 1 (1988), pp. 158\u2013173.","journal-title":"SIAM J. Disc. Math."},{"issue":"1","key":"36_CR7","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1007\/BF02579202","volume":"7","author":"J. Friedman","year":"1987","unstructured":"J. Friedman, N. Pippenger, Expanding Graphs Contain All Small Trees, Combinatorica 7 (1) (1987), pp.71\u201376.","journal-title":"Combinatorica"},{"key":"36_CR8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/BF02808204","volume":"89","author":"P.E. Haxell","year":"1995","unstructured":"P.E. Haxell, Y. Kohayakawa, The Size-Ramsey Number of Trees, Israel J. of Mathematics 89 (1995), pp. 261\u2013274.","journal-title":"Israel J. of Mathematics"},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/0196-6774(84)90022-1","volume":"5","author":"D.S. Johnson","year":"1984","unstructured":"D.S. Johnson, The NP-Completeness Column: An Ongoing Guide, J. of Algorithms 5 (1984), pp. 433\u2013447.","journal-title":"J. of Algorithms"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"D.S. Johnson, A Catalog of Complexity Classes, in Handbook of Theoretical Computer Science, Vol. A (J. Van Leeuwen, ed.), Elsevier 1990, pp. 67\u2013162.","DOI":"10.1016\/B978-0-444-88071-0.50007-2"},{"key":"36_CR11","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1006\/jcom.1995.1005","volume":"11","author":"L. Khachiyan","year":"1995","unstructured":"L. Khachiyan, On the Complexity of Approximating Extremal Determinants in Matrices, J. of Complexity 11 (1995), pp.138\u2013153.","journal-title":"J. of Complexity"},{"key":"36_CR12","unstructured":"J. Oxley, Matroid Theory, Oxford University Press, 1992."},{"key":"36_CR13","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1016\/0022-0000(84)90068-0","volume":"28","author":"C.H. Papadimitriou","year":"1984","unstructured":"C.H. Papadimitriou, M. Yannakakis, The Complexity of Facets (And Some Facets of Complexity), J. Comput. System Sci. 28 (1984), pp.244\u2013259.","journal-title":"J. Comput. System Sci."},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"M.J. Piff, D.J.A. Welsh, On the vector representation of matroids, J. London Math. Soc. (2) 2, pp. 284\u2013288.","DOI":"10.1112\/jlms\/s2-2.2.284"},{"key":"36_CR15","volume-title":"Theory of Integer and Linear Programming","author":"A. Schrijver","year":"1986","unstructured":"A. Schrijver, Theory of Integer and Linear Programming, Wiley, Chichester, 1986."},{"key":"36_CR16","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"J.T. Schwartz, Fast Probabilistic Algorithms For Verification of Polynomial Identities, Journal of the ACM 27 (1980), pp.701\u2013717.","journal-title":"Journal of the ACM"},{"key":"36_CR17","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1016\/0304-3975(86)90135-0","volume":"47","author":"L.G. Valiant","year":"1986","unstructured":"L.G. Valiant, V. Vazirani, NP Is As Easy As Detecting Unique Solutions, Theoretical Computer Science 47 (1986), pp.85\u201393.","journal-title":"Theoretical Computer Science"},{"key":"36_CR18","unstructured":"A. Vardy, The Intractability of Computing the Minimum Distance of a Code, manuscript November 1996."},{"key":"36_CR19","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/0304-3975(83)90004-X","volume":"24","author":"U.V. Vazirani","year":"1983","unstructured":"U.V. Vazirani, V.V. Vazirani, A Natural Encoding Scheme Proved Probabilistic Polynomial Complete, Theoretical Computer Science 24 (1983), pp. 291\u2013300.","journal-title":"Theoretical Computer Science"},{"key":"36_CR20","doi-asserted-by":"crossref","unstructured":"D.J.A. Welsh, Complexity: Knots, Colourings and Counting, Cambridge University Press, 1993.","DOI":"10.1017\/CBO9780511752506"},{"key":"36_CR21","doi-asserted-by":"crossref","unstructured":"R.E. Zippel, Probabilistic Algorithms for Sparse Polynomials, In Proceedings of EUROSAM 79, volume 72 of Lecture Notes in Computer Science, (1979), pp. 216\u2013226.","DOI":"10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63890-3_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,27]],"date-time":"2019-05-27T20:38:24Z","timestamp":1558989504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63890-3_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540638902","9783540696629"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-63890-3_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}