{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T17:10:11Z","timestamp":1781629811003,"version":"3.54.5"},"reference-count":44,"publisher":"Wiley","issue":"6","license":[{"start":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T00:00:00Z","timestamp":1775865600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"},{"start":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T00:00:00Z","timestamp":1775865600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/doi.wiley.com\/10.1002\/tdm_license_1.1"}],"funder":[{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["2022.12082.BD"],"award-info":[{"award-number":["2022.12082.BD"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UID\/00326\/2025"],"award-info":[{"award-number":["UID\/00326\/2025"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001871","name":"Funda\u00e7\u00e3o para a Ci\u00eancia e a Tecnologia","doi-asserted-by":"publisher","award":["UID\/04561\/2025"],"award-info":[{"award-number":["UID\/04561\/2025"]}],"id":[{"id":"10.13039\/501100001871","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Int Trans Operational Res"],"published-print":{"date-parts":[[2026,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>Given an undirected graph , a quasi\u2010clique is a subgraph of  with density at least  . Two optimisation problems can be defined for quasi\u2010cliques: the maximum quasi\u2010clique (MQC) problem, which finds a quasi\u2010clique with maximum vertex cardinality, and the densest \u2010subgraph (DKS) problem, which finds the densest subgraph of a given fixed cardinality. Most existing approaches to solving both problems often disregard the requirement of connectedness, leading to unconnected solutions that may be meaningless for many real\u2010life applications. To address this issue, we propose two flow\u2010based and an Miller\u2013Tucher\u2013Zemlin\u2010based connectedness constraint for integration into existing mixed\u2010integer linear programming (MILP) formulations for MQC and DKS. We compare MILP formulations enhanced with our connectedness constraints in terms of both running time and number of solved instances against existing approaches that ensure quasi\u2010clique connectedness. Experimental results demonstrate that our constraints are competitive, making them valuable for practical applications requiring\u00a0connectedness.<\/jats:p>","DOI":"10.1111\/itor.70184","type":"journal-article","created":{"date-parts":[[2026,4,11]],"date-time":"2026-04-11T09:39:03Z","timestamp":1775900343000},"page":"3800-3824","update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Ensuring connectedness for the maximum quasi\u2010clique and densest\n                    <i>k<\/i>\n                    \u2010subgraph problems"],"prefix":"10.1111","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1034-0589","authenticated-orcid":false,"given":"Daniela Scherer dos","family":"Santos","sequence":"first","affiliation":[{"name":"University of Coimbra, CISUC\/LASI, DEI Coimbra Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kathrin","family":"Klamroth","sequence":"additional","affiliation":[{"name":"School of Mathematics and Natural Sciences University of Wuppertal Wuppertal Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pedro","family":"Martins","sequence":"additional","affiliation":[{"name":"Coimbra Business School \u2010 ISCAC Polytechnic Institute of Coimbra Coimbra Portugal"},{"name":"Center for Mathematical Studies \u2010 CEMS.UL Lisbon Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[{"name":"University of Coimbra, CISUC\/LASI, DEI Coimbra Portugal"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2026,4,11]]},"reference":[{"key":"e_1_2_9_2_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/050\/06"},{"key":"e_1_2_9_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45995-2_51"},{"key":"e_1_2_9_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12691-3_21"},{"key":"e_1_2_9_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0015413"},{"key":"e_1_2_9_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1999.1062"},{"key":"e_1_2_9_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkr1227"},{"key":"e_1_2_9_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-7997-1_9"},{"key":"e_1_2_9_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806719"},{"key":"e_1_2_9_10_1","doi-asserted-by":"crossref","unstructured":"Bhattacharyya M. Bandyopadhyay S. 2009.Mining the largest quasi\u2010clique in human protein interactome. In the2009 International Conference on Adaptive and Intelligent Systems.IEEE Piscataway NJ pp.194\u2013199.","DOI":"10.1109\/ICAIS.2009.39"},{"key":"e_1_2_9_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/03155986.2005.11732724"},{"key":"e_1_2_9_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36065-7_12"},{"key":"e_1_2_9_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92695-5_4"},{"key":"e_1_2_9_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.04.009"},{"key":"e_1_2_9_15_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v35i14.17455"},{"key":"e_1_2_9_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2017.07.003"},{"key":"e_1_2_9_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90088-X"},{"key":"e_1_2_9_18_1","doi-asserted-by":"crossref","unstructured":"Davis T. A. Hu Y. 2011.The University of Florida sparse matrix collection.ACM Transactions on Mathematical Software38 1 article 1.","DOI":"10.1145\/2049662.2049663"},{"key":"e_1_2_9_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13520-0_14"},{"key":"e_1_2_9_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.04.040"},{"key":"e_1_2_9_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2024.12.018"},{"key":"e_1_2_9_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010050"},{"key":"e_1_2_9_23_1","unstructured":"Feige U. Seltser M. 1997.On the densest k\u2010subgraph problems. Technical Report CS97\u201016 Weizmann Institute Department of Applied Math and Computer Science Rehovot Israel."},{"key":"e_1_2_9_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"e_1_2_9_25_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120402"},{"key":"e_1_2_9_26_1","unstructured":"Gschwind T. Irnich S. Furini F. Calvo R. W. 2015.social network analysis and community detection by decomposing a graph into relaxed cliques. Working Papers 1520 Gutenberg School of Management and Economics Johannes Gutenberg\u2010Universit\u00e4t Mainz."},{"key":"e_1_2_9_27_1","unstructured":"Hochbaum D. S. Pathria A. 1994.Node\u2010optimal connected k\u2010subgraphs. Manuscript UC Berkeley."},{"key":"e_1_2_9_28_1","doi-asserted-by":"crossref","unstructured":"Komusiewicz C. Sommer F. 2020.Fixcon: a generic solver for fixed\u2010cardinality subgraph problems. In Blelloch G.E. Finocchi I. (eds)Proceedings of the Symposium on Algorithm Engineering and Experiments ALENEX 2020 Salt Lake City UT USA January 5\u20106 2020.SIAM Philadelphia PA pp.12\u201326.","DOI":"10.1137\/1.9781611976007.2"},{"key":"e_1_2_9_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-20086-6_7"},{"key":"e_1_2_9_30_1","doi-asserted-by":"crossref","unstructured":"Kortsarz G. Peleg D. 1993.On choosing a dense subgraph. In theProceedings of the 1993 IEEE 34th Annual Foundations of Computer Science.IEEE Piscataway NJ pp.692\u2013701.","DOI":"10.1109\/SFCS.1993.366818"},{"key":"e_1_2_9_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.03.016"},{"key":"e_1_2_9_32_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021525624027"},{"key":"e_1_2_9_33_1","doi-asserted-by":"crossref","unstructured":"Marinelli F. Pizzuti A. Rossi F. 2021.Lp\u2010based dual bounds for the maximum quasi\u2010clique problem.Discrete Applied Mathematics296 118\u2013140. 16th Cologne\u2013Twente Workshop on Graphs and Combinatorial Optimization (CTW 2018).","DOI":"10.1016\/j.dam.2020.02.003"},{"key":"e_1_2_9_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/321043.321046"},{"key":"e_1_2_9_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-012-1242-y"},{"key":"e_1_2_9_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.019"},{"key":"e_1_2_9_37_1","doi-asserted-by":"crossref","unstructured":"Pattillo J. Youssef N. Butenko S. 2012. Clique relaxation models in social network analysis. In Thai M.T. Pardalos P.M. (eds)Handbook of Optimization in Complex Networks: Communication and Social Networks. Springer New York New York pp. 143\u2013162.","DOI":"10.1007\/978-1-4614-0857-4_5"},{"key":"e_1_2_9_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2021.06.094"},{"key":"e_1_2_9_39_1","doi-asserted-by":"publisher","DOI":"10.1051\/ro\/2020003"},{"key":"e_1_2_9_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.05.071"},{"key":"e_1_2_9_41_1","doi-asserted-by":"publisher","DOI":"10.1111\/itor.12637"},{"key":"e_1_2_9_42_1","doi-asserted-by":"crossref","unstructured":"Rossi R. A. Ahmed N. K. 2015.The network data repository with interactive graph analytics and visualization. InProceedings of the Twenty\u2010Ninth AAAI Conference on Artificial Intelligence.AAAI Press Austin TX pp.4292\u20134293.","DOI":"10.1609\/aaai.v29i1.9277"},{"key":"e_1_2_9_43_1","unstructured":"Trick M. 2002.Graph coloring instances.https:\/\/mat.tepper.cmu.edu\/COLOR\/instances.html(accessed 2 December 2022)."},{"key":"e_1_2_9_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-015-9804-y"},{"key":"e_1_2_9_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2020.03.019"}],"container-title":["International Transactions in Operational Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/itor.70184","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/full-xml\/10.1111\/itor.70184","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1111\/itor.70184","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T16:40:00Z","timestamp":1781628000000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1111\/itor.70184"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,11]]},"references-count":44,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2026,11]]}},"alternative-id":["10.1111\/itor.70184"],"URL":"https:\/\/doi.org\/10.1111\/itor.70184","archive":["Portico"],"relation":{},"ISSN":["0969-6016","1475-3995"],"issn-type":[{"value":"0969-6016","type":"print"},{"value":"1475-3995","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,11]]},"assertion":[{"value":"2025-04-10","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-02","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-04-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}