{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T03:54:30Z","timestamp":1777694070755,"version":"3.51.4"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2017,11,18]],"date-time":"2017-11-18T00:00:00Z","timestamp":1510963200000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/H023151\/1"],"award-info":[{"award-number":["EP\/H023151\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s10589-017-9967-9","type":"journal-article","created":{"date-parts":[[2017,11,18]],"date-time":"2017-11-18T03:14:03Z","timestamp":1510974843000},"page":"653-676","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["A two-level graph partitioning problem arising in mobile wireless communications"],"prefix":"10.1007","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5134-4397","authenticated-orcid":false,"given":"Jamie","family":"Fairbrother","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adam N.","family":"Letchford","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Keith","family":"Briggs","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,18]]},"reference":[{"issue":"1","key":"9967_CR1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10479-007-0178-0","volume":"153","author":"KI Aardal","year":"2007","unstructured":"Aardal, K.I., van Hoesel, S.P.M., Koster, A.M.C.A., Mannino, C., Sassano, A.: Models and solution techniques for frequency assignment problems. Ann. Oper. Res. 153(1), 79\u2013127 (2007)","journal-title":"Ann. Oper. Res."},{"key":"9967_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2016.04.002","volume":"211","author":"Z Ales","year":"2016","unstructured":"Ales, Z., Knippel, A., Pauchet, A.: Polyhedral combinatorics of the $$k$$ k -partitioning problem with representative variables. Discrete Appl. Math. 211, 1\u201314 (2016)","journal-title":"Discrete Appl. Math."},{"key":"9967_CR3","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/978-3-642-38189-8_15","volume-title":"Facets of Combinatorial Optimization","author":"MF Anjos","year":"2013","unstructured":"Anjos, M.F., Ghaddar, B., Hupp, L., Liers, F., Wiegele, A.: Solving $$k$$ k -way graph partitioning problems to optimality: the impact of semidefinite relaxations and the bundle method. In: J\u00fcnger, M., Reinelt, G. (eds.) Facets of Combinatorial Optimization, pp. 355\u2013386. Springer, Berlin (2013)"},{"key":"9967_CR4","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/PL00011381","volume":"88","author":"R Bornd\u00f6rfer","year":"2000","unstructured":"Bornd\u00f6rfer, R., Weismantel, R.: Set packing relaxations of integer programs. Math. Program. 88, 425\u2013450 (2000)","journal-title":"Math. Program."},{"issue":"9","key":"9967_CR5","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1145\/362342.362367","volume":"16","author":"C Bron","year":"1973","unstructured":"Bron, C., Kerbosch, J.: Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16(9), 575\u2013577 (1973). https:\/\/doi.org\/10.1145\/362342.362367","journal-title":"Commun. ACM"},{"key":"9967_CR6","first-page":"221","volume":"74","author":"A Caprara","year":"1996","unstructured":"Caprara, A., Fischetti, M.: $$\\{0,\\frac{1}{2}\\}$$ { 0 , 1 2 } -Chv\u00e1tal-Gomory cuts. Math. Program. 74, 221\u2013235 (1996)","journal-title":"Math. Program."},{"issue":"1","key":"9967_CR7","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1287\/opre.14.1.52","volume":"14","author":"RC Carlson","year":"1966","unstructured":"Carlson, R.C., Nemhauser, G.L.: Scheduling to minimize interaction cost. Oper. Res. 14(1), 52\u201358 (1966)","journal-title":"Oper. Res."},{"key":"9967_CR8","unstructured":"Chatziafratis, V., Charikar, M.: Approximate hierarchical clustering via sparsest cut and spreading metrics. In: P.\u00a0Klein (ed.) Proceedings of SODA 2017, to appear. SIAM, Philadelphia, PA (2017)"},{"issue":"1\u20133","key":"9967_CR9","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.R.: The partition problem. Math. Program. 59(1\u20133), 87\u2013115 (1993)","journal-title":"Math. Program."},{"issue":"1","key":"9967_CR10","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0166-218X(93)E0175-X","volume":"61","author":"S Chopra","year":"1995","unstructured":"Chopra, S., Rao, M.R.: Facets of the $$k$$ k -partition polytope. Discrete Appl. Math. 61(1), 27\u201348 (1995)","journal-title":"Discrete Appl. Math."},{"key":"9967_CR11","unstructured":"Christof, T., L\u00f6bel, A., Stoer, M.: PORTA\u2014a polyhedron representation transformation algorithm. Software package, available for download at http:\/\/www.zib.de\/Optimization\/Software\/Porta (1997)"},{"key":"9967_CR12","unstructured":"Csardi, G., Nepusz, T.: The igraph software package for complex network research. InterJournal Complex Syst. 1695 (2006). http:\/\/igraph.org"},{"key":"9967_CR13","doi-asserted-by":"crossref","unstructured":"Dasgupta, S.: A cost function for similarity-based hierarchical clustering. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing, pp. 118\u2013127. ACM (2016)","DOI":"10.1145\/2897518.2897527"},{"key":"9967_CR14","unstructured":"de Sousa, V.J.R., Anjos, M.F., Le Digabel, S.: Computational study of valid inequalities for the maximum $$k$$ k -cut problem. Working paper, available on optimization online (2016)"},{"key":"9967_CR15","volume-title":"Applied Geometry and Discrete Mathematics","author":"M Deza","year":"1990","unstructured":"Deza, M., Gr\u00f6tschel, M., Laurent, M.: Complete descriptions of small multicut polytopes. In: Gritzmann, P., Sturmfelds, B. (eds.) Applied Geometry and Discrete Mathematics. AMS, Philadelphia (1990)"},{"issue":"4","key":"9967_CR16","doi-asserted-by":"crossref","first-page":"981","DOI":"10.1287\/moor.17.4.981","volume":"17","author":"M Deza","year":"1992","unstructured":"Deza, M., Gr\u00f6tschel, M., Laurent, M.: Clique-web facets for multicut polytopes. Math. Oper. Res. 17(4), 981\u20131000 (1992)","journal-title":"Math. Oper. Res."},{"key":"9967_CR17","unstructured":"Eisenbl\u00e4tter, A.: Frequency assignment in GSM networks: Models, heuristics, and lower bounds. Ph.D. thesis, Technical University of Berlin (2001)"},{"key":"9967_CR18","doi-asserted-by":"crossref","unstructured":"Eisenbl\u00e4tter, A.: The semidefinite relaxation of the $$k$$ k -partition polytope is strong. In: W.J. Cook, A.S. Schulz (eds.) Proceedings of IPCO IX, pp. 273\u2013290. Springer, Berlin (2002)","DOI":"10.1007\/3-540-47867-1_20"},{"key":"9967_CR19","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Cheong, O., Chwa, K., Park, K. (eds.) Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15\u201317, 2010, Proceedings, Part I, pp. 403\u2013414. Springer, Berlin\/Heidelberg (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"9967_CR20","doi-asserted-by":"publisher","unstructured":"Fairbrother, J., Letchford, A.N.: Projection results for the k-partition problem. Discrete Optim. (2017). https:\/\/doi.org\/10.1016\/j.disopt.2017.08.001 . http:\/\/www.sciencedirect.com\/science\/article\/pii\/S1572528617301718","DOI":"10.1016\/j.disopt.2017.08.001"},{"issue":"1","key":"9967_CR21","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/BF02523688","volume":"18","author":"A Frieze","year":"1997","unstructured":"Frieze, A., Jerrum, M.: Improved approximation algorithms for max $$k$$ k -cut and max bisection. Algorithmica 18(1), 67\u201381 (1997)","journal-title":"Algorithmica"},{"issue":"1","key":"9967_CR22","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s10479-008-0481-4","volume":"188","author":"B Ghaddar","year":"2011","unstructured":"Ghaddar, B., Anjos, M.F., Liers, F.: A branch-and-cut algorithm based on semidefinite programming for the minimum $$k$$ k -partition problem. Ann. Oper. Res. 188(1), 155\u2013174 (2011)","journal-title":"Ann. Oper. Res."},{"key":"9967_CR23","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-97881-4","volume-title":"Geometric Algorithms and Combinatorial Optimization","author":"M Gr\u00f6tschel","year":"1988","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer, Berlin (1988)"},{"issue":"1\u20133","key":"9967_CR24","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45(1\u20133), 59\u201396 (1989)","journal-title":"Math. Program."},{"issue":"1\u20133","key":"9967_CR25","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1007\/BF01580870","volume":"47","author":"M Gr\u00f6tschel","year":"1990","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: Facets of the clique partitioning polytope. Math. Program. 47(1\u20133), 367\u2013387 (1990)","journal-title":"Math. Program."},{"key":"9967_CR26","unstructured":"Gurobi\u00a0Optimization, I.: Gurobi optimizer reference manual (2016). http:\/\/www.gurobi.com"},{"issue":"2\u20133","key":"9967_CR27","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1016\/0166-218X(93)90046-Q","volume":"42","author":"DS Hochbaum","year":"1993","unstructured":"Hochbaum, D.S.: Why should biconnected components be identified first [sic]. Discrete Appl. Math. 42(2\u20133), 203\u2013210 (1993)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"9967_CR28","doi-asserted-by":"crossref","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft, J., Tarjan, R.: Algorithm 447: efficient algorithms for graph manipulation. Commun. ACM 16(6), 372\u2013378 (1973)","journal-title":"Commun. ACM"},{"key":"9967_CR29","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1016\/j.disopt.2011.07.001","volume":"8","author":"V Kaibel","year":"2011","unstructured":"Kaibel, V., Peinhardt, M., Pfetsch, M.E.: Orbitopal fixing. Discrete Optim. 8, 595\u2013610 (2011)","journal-title":"Discrete Optim."},{"key":"9967_CR30","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1023\/A:1011493126498","volume":"5","author":"AN Letchford","year":"2001","unstructured":"Letchford, A.N.: On disjunctive cuts for combinatorial optimization. J. Comb. Optim. 5, 299\u2013315 (2001)","journal-title":"J. Comb. Optim."},{"issue":"4","key":"9967_CR31","doi-asserted-by":"crossref","first-page":"888","DOI":"10.3724\/SP.J.1001.2008.00888","volume":"19","author":"G Lu","year":"2010","unstructured":"Lu, G., Zhou, M.T., Niu, X.Z., She, K., Tang, Y., Qin, K.: A survey of proximity graphs in wireless networks. J. Softw. 19(4), 888\u2013911 (2010)","journal-title":"J. Softw."},{"key":"9967_CR32","unstructured":"Mannino, C., Rossi, F., Rossi, F., Smriglio, S.: A unified view in planning broadcasting networks. In: D.\u00a0Kurlander, M.\u00a0Brown, R.\u00a0Rao (eds.) Proceedings of INOC 2007, pp. 41\u201350 (2007)"},{"key":"9967_CR33","doi-asserted-by":"crossref","first-page":"647","DOI":"10.1007\/978-3-540-68279-0_17","volume-title":"50 Years of Integer Programming 1958\u20132008","author":"F Margot","year":"2010","unstructured":"Margot, F.: Symmetry in integer linear programming. In: J\u00fcnger, M., et al. (eds.) 50 Years of Integer Programming 1958\u20132008, pp. 647\u2013686. Springer, Berlin (2010)"},{"issue":"1","key":"9967_CR34","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/BF02760024","volume":"3","author":"JW Moon","year":"1965","unstructured":"Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3(1), 23\u201328 (1965). https:\/\/doi.org\/10.1007\/BF02760024","journal-title":"Israel J. Math."},{"key":"9967_CR35","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1137\/S1052623499363256","volume":"13","author":"R M\u00fcller","year":"2002","unstructured":"M\u00fcller, R., Schulz, A.S.: Transitive packing: a unifying concept in combinatorial optimization. SIAM J. Optim. 13, 335\u2013367 (2002)","journal-title":"SIAM J. Optim."},{"key":"9967_CR36","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1002\/net.10004","volume":"38","author":"M Oosten","year":"2009","unstructured":"Oosten, M., Rutten, J.H.G.C., Spieksma, F.C.R.: The clique partitioning problem: facets and patching facets. Networks 38, 209\u2013226 (2009)","journal-title":"Networks"},{"issue":"4","key":"9967_CR37","first-page":"321","volume":"10","author":"F Rendl","year":"2012","unstructured":"Rendl, F.: Semidefinite relaxations for partitioning, assignment and ordering problems. 40R 10(4), 321\u2013346 (2012)","journal-title":"40R"},{"key":"9967_CR38","volume-title":"Handbook of Optimization in Telecommunications","year":"2007","unstructured":"Resende, M., Pardalos, P. (eds.): Handbook of Optimization in Telecommunications. Springer, New York (2007)"},{"key":"9967_CR39","unstructured":"Roy, A., Pokutta, S.: Hierarchical clustering via spreading metrics. In: Advances in Neural Information Processing Systems, pp. 2316\u20132324 (2016)"},{"key":"9967_CR40","doi-asserted-by":"crossref","unstructured":"Sanders, P., Schulz, C.: Engineering multilevel graph partitioning algorithms. In: Demetrescu, C., Halld\u00f3rsson, M.M. (eds.) Proceedings of ESA 2011, Lecture Notes in Computer Science, vol. 6942. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-23719-5_40"},{"issue":"3","key":"9967_CR41","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/0378-8733(83)90028-X","volume":"5","author":"SB Seidman","year":"1983","unstructured":"Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269\u2013287 (1983)","journal-title":"Soc. Netw."},{"issue":"1","key":"9967_CR42","doi-asserted-by":"crossref","first-page":"16","DOI":"10.1287\/ijoc.1120.0542","volume":"26","author":"R Sotirov","year":"2013","unstructured":"Sotirov, R.: An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J. Comput. 26(1), 16\u201330 (2013)","journal-title":"INFORMS J. Comput."},{"issue":"1","key":"9967_CR43","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0021-9800(68)80081-X","volume":"4","author":"G Szekeres","year":"1968","unstructured":"Szekeres, G., Wilf, H.S.: An inequality for the chromatic number of a graph. J. Comb. Theory 4(1), 1\u20133 (1968)","journal-title":"J. Comb. Theory"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10589-017-9967-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9967-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-017-9967-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,6]],"date-time":"2019-10-06T05:30:22Z","timestamp":1570339822000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10589-017-9967-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,18]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["9967"],"URL":"https:\/\/doi.org\/10.1007\/s10589-017-9967-9","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,18]]}}}