{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,19]],"date-time":"2023-10-19T04:53:23Z","timestamp":1697691203414},"reference-count":31,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,9,12]],"date-time":"2006-09-12T00:00:00Z","timestamp":1158019200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/http\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[2006,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The present work tackles a recent problem in the class of cardinality constrained combinatorial optimization problems for the planar graph case: the minimum <jats:italic>k<\/jats:italic>\u2010cardinality cut problem. Given an undirected edge\u2010weighted connected graph the min <jats:italic>k<\/jats:italic>\u2010cardinality cut problem consists in finding a partition of the vertex set <jats:italic>V<\/jats:italic> in two sets <jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub>, <jats:italic>V<\/jats:italic><jats:sub>2<\/jats:sub> such that the number of the edges between <jats:italic>V<\/jats:italic><jats:sub>1<\/jats:sub> and <jats:italic>V<\/jats:italic><jats:sub>2<\/jats:sub> is exactly <jats:italic>k<\/jats:italic> and the sum of the weights of these edges is minimal. Although for general graphs the problem is already strongly <jats:italic>\ud835\udca9<\/jats:italic><jats:italic>\ud835\udcab<\/jats:italic>\u2010hard, we have found a pseudopolynomial algorithm for the planar graph case. This algorithm is based on the fact that the min <jats:italic>k<\/jats:italic>\u2010cardinality cut problem in the original graph is equivalent to a bi\u2010weighted exact perfect matching problem in a suitable transformation of the geometric dual graph. Because the Lagrangian relaxation of cardinality constraint yields a max cut problem and max cut is polynomially solvable in planar graphs, we also develop a Lagrangian heuristic for the min <jats:italic>k<\/jats:italic>\u2010cardinality cut in planar graphs. We compare the performance of this heuristic with the performance of a more general heuristic based on a Semidefinite Programming relaxation and on the Goemans and Williamson's random hyperplane technique. \u00a9 2006\u00a0Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 195\u2013208 2006<\/jats:p>","DOI":"10.1002\/net.20129","type":"journal-article","created":{"date-parts":[[2006,9,12]],"date-time":"2006-09-12T20:54:10Z","timestamp":1158094450000},"page":"195-208","source":"Crossref","is-referenced-by-count":1,"title":["Solving minimum K\u2010cardinality cut problems in planar graphs"],"prefix":"10.1002","volume":"48","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":"Marco","family":"Trubian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,9,12]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580600"},{"key":"e_1_2_1_2_3","unstructured":"F. Barahona 1990 Springer Berlin"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.36.3.493"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(87)90067-9"},{"key":"e_1_2_1_5_2","volume-title":"Introduction to Linear Optimization, 217:221","author":"Bertsimas D.","year":"1997"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805765"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(03)00358-5"},{"key":"e_1_2_1_8_2","volume-title":"Finite Graphs and Networks: An Introduction with Applications","author":"Busacker R. G.","year":"1965"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90018-8"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0305-0548(99)00074-X"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.273754"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(97)00120-0"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.6028\/jres.071B.033"},{"issue":"1","key":"e_1_2_1_14_2","first-page":"87","article-title":"Heuristics for the k\u2010cardinality tree and subgraph problem","volume":"14","author":"Ehrgott M.","year":"1997","journal-title":"Asia Pacific J Oper Res"},{"key":"e_1_2_1_15_2","unstructured":"M.Ehrgott H.W.Hamacher F.Maffioli Fixed cardinality combinatorial optimization problems\u2014A survey Report in Wirtschaftsmathematik 56 (1999) Fachbereich Mathematik Universit\u00e4t Kaiserslautern."},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018925728178"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)00034-J"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1999.0522"},{"key":"e_1_2_1_19_2","volume-title":"Computers and Intractability: A Guide to the Theory of NP\u2010Completeness","author":"Garey M.R.","year":"1979"},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.24.2.383"},{"key":"e_1_2_1_22_2","first-page":"22","volume-title":"Finding a maximum matching is in RNC","author":"Karp R.M.","year":"1985"},{"key":"e_1_2_1_23_2","first-page":"565","article-title":"On determinants, matchings and random algorithms","volume":"79","author":"Lovasz L.","year":"1979","journal-title":"Fund Comput Theo"},{"key":"e_1_2_1_24_2","first-page":"322","article-title":"Annals of Discrete Mathematics (29)","author":"Lovasz L.","journal-title":"Matching theory"},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_26_2","doi-asserted-by":"publisher","DOI":"10.1002\/9781118627372"},{"key":"e_1_2_1_27_2","first-page":"502","article-title":"Finding the maximum cut in a graph","volume":"10","author":"Orlova G.I.","year":"1972","journal-title":"Engineering Cybernetics"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01580850"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263872"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04565-7"},{"key":"e_1_2_1_31_2","doi-asserted-by":"crossref","unstructured":"J.Von Zur Gathen Parallel algorithms for algebraic problems Proceedings 15th ACM STOC 1983 pp.17\u201323.","DOI":"10.1145\/800061.808728"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.20129","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.20129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,18]],"date-time":"2023-10-18T13:04:04Z","timestamp":1697634244000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/onlinelibrary.wiley.com\/doi\/10.1002\/net.20129"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9,12]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,12]]}},"alternative-id":["10.1002\/net.20129"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1002\/net.20129","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"value":"0028-3045","type":"print"},{"value":"1097-0037","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9,12]]}}}