{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T16:38:13Z","timestamp":1777653493577,"version":"3.51.4"},"reference-count":32,"publisher":"Elsevier BV","issue":"3","license":[{"start":{"date-parts":[[2004,3,1]],"date-time":"2004-03-01T00:00:00Z","timestamp":1078099200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,8,22]],"date-time":"2013-08-22T00:00:00Z","timestamp":1377129600000},"content-version":"vor","delay-in-days":3461,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Applied Mathematics"],"published-print":{"date-parts":[[2004,3]]},"DOI":"10.1016\/s0166-218x(03)00358-5","type":"journal-article","created":{"date-parts":[[2003,8,8]],"date-time":"2003-08-08T00:37:32Z","timestamp":1060303052000},"page":"311-341","source":"Crossref","is-referenced-by-count":17,"title":["Cardinality constrained minimum cut problems: complexity and algorithms"],"prefix":"10.1016","volume":"137","author":[{"given":"Maurizio","family":"Bruglieri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Francesco","family":"Maffioli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Matthias","family":"Ehrgott","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0166-218X(03)00358-5_BIB1","doi-asserted-by":"crossref","unstructured":"A.A. Ageev, M.I. Sviridenko, Approximation algorithms for maximum coverage and max-cut with given sizes of parts, in: Integer Programming and Combinatorial Optimization, Lecture Notes in Computer Science, Vol. 1610, Springer, Berlin, 1999, pp. 17\u201330.","DOI":"10.1007\/3-540-48777-8_2"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB2","series-title":"On some applications of the Chinese postman problem, in: Algorithms and Combinatorics: Paths, Flows, and VLSI-Layout","author":"Barahona","year":"1990"},{"issue":"3","key":"10.1016\/S0166-218X(03)00358-5_BIB3","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1287\/opre.36.3.493","article-title":"An application of combinatorial optimization to statistical physics and circuit layout design","volume":"36","author":"Barahona","year":"1988","journal-title":"Oper. Res."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB4","doi-asserted-by":"crossref","unstructured":"B. Borchers, CSDP, a C library for semidefinite programming, Optimization Methods and Software 11 (1999) 613\u2013623, http:\/\/www.nmt.edu\/~borchers\/csdp.html.","DOI":"10.1080\/10556789908805765"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB5","unstructured":"M. Bruglieri, K-Cardinality cut problems, Ph.D. Thesis, Dottorato MA.C.R.O., Department of Mathematics \u2018F. Enriquez\u2019, University of Milan, 2000. Available at www.elet.polimi.it\/upload\/bruglier\/kcut\/PhD-thesis.zip."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB6","series-title":"Finite Graphs and Networks: An Introduction with Applications","author":"Busacker","year":"1965"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB7","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/BF02115754","article-title":"The image of weighted combinatorial problems","volume":"33","author":"Camerini","year":"1991","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB8","doi-asserted-by":"crossref","first-page":"1271","DOI":"10.1016\/S0305-0548(99)00074-X","article-title":"Heuristics for cardinality constrained portfolio optimisation","volume":"27","author":"Chang","year":"2000","journal-title":"Comput. Operat. Res."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB9","series-title":"Annotated Bibliographies in Combinatorial Optimization","author":"Dell'Amico","year":"1997"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB10","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1016\/S0166-218X(97)00120-0","article-title":"The k-cardinality assignment problem","volume":"76","author":"Dell'Amico","year":"1997","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB11","doi-asserted-by":"crossref","first-page":"241","DOI":"10.6028\/jres.071B.033","article-title":"Systems of distinct representatives and linear algebra","volume":"71B","author":"Edmonds","year":"1967","journal-title":"J. Res. Natl. Bur. Standards"},{"issue":"1","key":"10.1016\/S0166-218X(03)00358-5_BIB12","first-page":"87","article-title":"Heuristics for the k-cardinality tree and subgraph problem","volume":"14","author":"Ehrgott","year":"1997","journal-title":"Asia Pacific J. Oper. Res."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB13","unstructured":"M. Ehrgott, H.W. Hamacher, F. Maffioli, Fixed cardinality combinatorial optimization problems\u2014a survey, Report in Wirtschaftsmathematik 56 Fachbereich Mathematik, Universit\u00e4t Kaiserslautern, 1999."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB14","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1023\/A:1018925728178","article-title":"Integer programming approaches to facilities layout models with forbidden areas","volume":"81","author":"Foulds","year":"1998","journal-title":"Ann. Oper. Res."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB15","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","article-title":"Improved approximation algorithms for max k-cut and max bisection","volume":"18","author":"Frieze","year":"1997","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0166-218X(92)00034-J","article-title":"On the computation of Pfaffians","volume":"51","author":"Galbiati","year":"1994","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB17","series-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey","year":"1979"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB18","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph problems","volume":"1","author":"Garey","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB19","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02614315","article-title":"Semidefinite programming in combinatorial optimization","volume":"79","author":"Goemans","year":"1997","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB20","doi-asserted-by":"crossref","first-page":"1115","DOI":"10.1145\/227683.227684","article-title":"Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming","volume":"42","author":"Goemans","year":"1995","journal-title":"J. ACM"},{"issue":"2","key":"10.1016\/S0166-218X(03)00358-5_BIB21","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/s004530010013","article-title":"Approximation algorithms for minimum k-cut","volume":"27","author":"Guttmann-Beck","year":"2000","journal-title":"Algorithmica"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB22","unstructured":"D. Karger, Minimum cuts in near-linear time, http:\/\/theory.lcs.mit.edu\/\/~karger."},{"issue":"1","key":"10.1016\/S0166-218X(03)00358-5_BIB23","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/BF02579407","article-title":"Constructing a perfect matching is in Random NC","volume":"6","author":"Karp","year":"1986","journal-title":"Combinatorica"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB24","series-title":"The Theory of Matrices","author":"Lancaster","year":"1985"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB25","first-page":"565","article-title":"On determinants, matchings and random algorithms","volume":"79","author":"Lovasz","year":"1979","journal-title":"Fund. Comput. Theory"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB26","first-page":"502","article-title":"Finding the maximum cut in a graph","volume":"10","author":"Orlova","year":"1972","journal-title":"Eng. Cybernet."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB27","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1007\/BF01580850","article-title":"An efficient algorithm for the minimum capacity cut problem","volume":"47","author":"Padberg","year":"1990","journal-title":"Math. Programming"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB28","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1137\/0805024","article-title":"Nonpolyhedral relaxations of graph-bisection problems","volume":"5","author":"Poljak","year":"1995","journal-title":"SIAM J. Optim."},{"key":"10.1016\/S0166-218X(03)00358-5_BIB29","doi-asserted-by":"crossref","unstructured":"H. Saran, V. Vazirani, Finding k-cuts within twice the optimal, in: Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway NJ, 1991, pp. 743\u2013751.","DOI":"10.1109\/SFCS.1991.185443"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB30","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","article-title":"Fast probabilistic algorithms for verification of polynomial identities","volume":"27","author":"Schwartz","year":"1980","journal-title":"J. Assoc. Comput. Machinery"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB31","doi-asserted-by":"crossref","first-page":"585","DOI":"10.1145\/263867.263872","article-title":"A simple min-cut algorithm","volume":"44","author":"Stoer","year":"1997","journal-title":"J. ACM"},{"key":"10.1016\/S0166-218X(03)00358-5_BIB32","doi-asserted-by":"crossref","unstructured":"H. Wolkowicz, R. Saigal, L. Vandenberghe, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications, Kluwer Academic Publishers, Dordrecht, 2000.","DOI":"10.1007\/978-1-4615-4381-7"}],"container-title":["Discrete Applied Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X03003585?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0166218X03003585?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,3,15]],"date-time":"2019-03-15T06:23:04Z","timestamp":1552630984000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0166218X03003585"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,3]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2004,3]]}},"alternative-id":["S0166218X03003585"],"URL":"https:\/\/doi.org\/10.1016\/s0166-218x(03)00358-5","relation":{},"ISSN":["0166-218X"],"issn-type":[{"value":"0166-218X","type":"print"}],"subject":[],"published":{"date-parts":[[2004,3]]}}}