{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:16:55Z","timestamp":1725484615812},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424932"},{"type":"electronic","value":"9783540446767"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44676-1_43","type":"book-chapter","created":{"date-parts":[[2007,5,18]],"date-time":"2007-05-18T16:43:15Z","timestamp":1179506595000},"page":"512-523","source":"Crossref","is-referenced-by-count":2,"title":["Packing Cycles and Cuts in Undirected Graphs"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alessandro","family":"Panconesi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Romeo","family":"Rizzi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"43_CR1","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1002\/(SICI)1097-0118(199704)24:4<357::AID-JGT8>3.0.CO;2-N","volume":"24","author":"A.A. Ageev","year":"1997","unstructured":"A.A. Ageev, A.V. Kostochka, Z. Szigeti, A Characterization of Seymour Graphs. J. Graph Theory 24 (1997) 357\u2013364.","journal-title":"J. Graph Theory"},{"key":"43_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/3-540-48481-7_42","volume-title":"Proceedings of the 7th European Symposium on Algorithms (ESA\u201999)","author":"A.A. Ageev","year":"1999","unstructured":"A.A. Ageev, On Finding the Maximum Number of Disjoint Cuts in Seymour Graphs. Proceedings of the 7th European Symposium on Algorithms (ESA\u201999), Lecture Notes in Comput. Sci., 1643, Springer, Berlin (1999) 490\u2013497."},{"key":"43_CR3","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1137\/S0097539793250627","volume":"25","author":"V. Bafna","year":"1996","unstructured":"V. Bafna and P.A. Pevzner, Genome Rearrangements and Sorting by Reversals. SIAM J. on Computing 25 (1996) 272\u2013289.","journal-title":"SIAM J. on Computing"},{"key":"43_CR4","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"B.S. Baker, Approximation Algorithms for $$ \\mathcal{N}\\mathcal{P} $$ -Complete Problems on Planar Graphs. J. ACM 41 (1994) 153\u2013180.","journal-title":"J. ACM"},{"key":"43_CR5","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s002240000113","volume":"32","author":"P. Berman","year":"1999","unstructured":"P. Berman, T. Fujito, On Approximation Properties of the Independent Set Problem for Low Degree Graphs. Theory of Computing Systems 32 (1999) 115\u2013132.","journal-title":"Theory of Computing Systems"},{"key":"43_CR6","doi-asserted-by":"crossref","unstructured":"P. Berman and M. Karpinski, On Some Tighter Inapproximability Results. ECCC Report No. 29, University of Trier (1998).","DOI":"10.1007\/3-540-48523-6_17"},{"key":"43_CR7","volume-title":"Extremal Graph Theory","author":"B. Bollob\u00e1s","year":"1978","unstructured":"B. Bollob\u00e1s, Extremal Graph Theory, Academic Press, New-York (1978)."},{"key":"43_CR8","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01994876","volume":"32","author":"R. Boppana","year":"1992","unstructured":"R. Boppana, M.M. Halld\u00f3rsson, Approximating Maximum Independent Sets by Excluding Subgraphs. Bit 32 (1992) 180\u2013196.","journal-title":"Bit"},{"key":"43_CR9","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1137\/S089548019731994X","volume":"12","author":"A. Caprara","year":"1999","unstructured":"A. Caprara, Sorting Permutations by Reversals and Eulerian Cycle Decompositions. SIAM J. on Discrete Mathematics 12 (1999) 91\u2013110.","journal-title":"SIAM J. on Discrete Mathematics"},{"key":"43_CR10","unstructured":"C.J. Colbourn, The Combinatorics of Network Reliability. Oxford University Press (1986)."},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02992776","volume":"25","author":"G.A. Dirac","year":"1961","unstructured":"G.A. Dirac, On Rigid Circuit Graphs. Abh. Math. Sem. Univ. Hamburg 25 (1961) 71\u201376.","journal-title":"Abh. Math. Sem. Univ. Hamburg"},{"key":"43_CR12","doi-asserted-by":"crossref","first-page":"3","DOI":"10.5486\/PMD.1962.9.1-2.02","volume":"9","author":"P. Erd\u00f6s","year":"1962","unstructured":"P. Erd\u00f6s and L. P\u00f3sa. On the Maximal Number of Disjoint Circuits of a Graph. Publ. Math. Debrecen 9 (1962) 3\u201312.","journal-title":"Publ. Math. Debrecen"},{"key":"43_CR13","first-page":"251","volume":"12","author":"P. Erd\u00f6s","year":"1963","unstructured":"P. Erd\u00f6s and H. Sachs. Regulare Graphen Gegebener Taillenweite mit Minimaler Knotenzahl. Wittenberg Math.-Natur. Reine 12 (1963) 251\u2013257.","journal-title":"Wittenberg Math.-Natur. Reine"},{"key":"43_CR14","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/BF01202790","volume":"13","author":"A. Frank","year":"1993","unstructured":"A. Frank, Conservative Weightings and Ear-Decompositions of Graphs. Combinatorica 13 (1993) 65\u201381.","journal-title":"Combinatorica"},{"key":"43_CR15","first-page":"815","volume":"38","author":"H.N. Gabow","year":"1991","unstructured":"H.N. Gabow and R.E. Tarjan, Faster Scaling Algorithms for General Matching Problems. J. A CM 38 (1991) 815\u2013853.","journal-title":"J. A CM"},{"key":"43_CR16","isbn-type":"print","volume-title":"Algorithms and Combinatorics","author":"M. Grotschel","year":"1993","unstructured":"M. Grotschel, L. Lov\u00e1sz, A. Schrijver, Geometric algorithms and combinatorial optimization, Second edition: Algorithms and Combinatorics, 2. Springer-Verlag, Berlin, (1993). ISBN: 3-540-56740-2.","ISBN":"http:\/\/id.crossref.org\/isbn\/3540567402","edition":"Second edition"},{"key":"43_CR17","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/BF02392825","volume":"182","author":"J. H\u00e5stad","year":"2000","unstructured":"J. H\u00e5stad, Clique is Hard to Approximate within n1-\u03b5. Acta Mathematica 182 (2000) 105\u2013142.","journal-title":"Acta Mathematica"},{"key":"43_CR18","doi-asserted-by":"publisher","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I. Holyer","year":"1981","unstructured":"I. Holyer, The $$ \\mathcal{N}\\mathcal{P} $$ -Completeness of Some Edge-Partition Problems. SIAM J. on Computing 10 (1981) 713\u2013717.","journal-title":"SIAM J. on Computing"},{"key":"43_CR19","series-title":"Lect Notes Comput Sci","first-page":"424","volume-title":"Proceedings of the 2nd Euoropean Symposium on Algorithms (ESA\u201994)","author":"H.B. Hunt III","year":"1994","unstructured":"H.B. HuntIII, M.V. Marathe, V. Radhakrishnan, S.S. Ravi, D.J. Rosenkrantz and R.E. Stearns, A Unified Approach to Approximation Schemes for $$ \\mathcal{N}\\mathcal{P} $$ -and $$ \\mathcal{P}\\mathcal{S}\\mathcal{P}\\mathcal{A}\\mathcal{C}\\mathcal{E} $$ -Hard Problems for Geometric Graphs. Proceedings of the 2nd Euoropean Symposium on Algorithms (ESA\u201994), Lecture Notes in Comput. Sci., 855, Springer, Berlin (1994) 424\u2013435."},{"key":"43_CR20","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/BF01188586","volume":"13","author":"J. Kececioglu","year":"1995","unstructured":"J. Kececioglu and D. Sankoff, Exact and Approximation Algorithms for Sorting by Reversals, with Application to Genome Rearrangement. Algorithmica 13 (1995) 180\u2013210.","journal-title":"Algorithmica"},{"key":"43_CR21","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"D. Lichtenstein, Planar formulae and their uses. SIAM J. on Computing 11 (1982) 329\u2013343.","journal-title":"SIAM J. on Computing"},{"key":"43_CR22","unstructured":"L. Lov\u00e1sz, M.D. Plummer, Matching Theory, Akad\u00e9miai Kiad\u00f3 (1986)"},{"key":"43_CR23","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C.H. Papadimitriou","year":"1991","unstructured":"C.H. Papadimitriou and M. Yannakakis (1991), Optimization, Approximation, and Complexity Classes J. Comput. System Sci. 43 (1991) 425\u2013440.","journal-title":"J. Comput. System Sci."},{"key":"43_CR24","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1137\/0205021","volume":"5","author":"D.J. Rose","year":"1976","unstructured":"D.J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic Aspects of Vertex Elimination on Graphs. SIAM J. on Computing 5 (1976) 266\u2013283.","journal-title":"SIAM J. on Computing"}],"container-title":["Lecture Notes in Computer Science","Algorithms \u2014 ESA 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44676-1_43","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T22:18:56Z","timestamp":1683843536000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44676-1_43"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424932","9783540446767"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/3-540-44676-1_43","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}