EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Ensuring connectedness for the maximum quasi‐clique and densest k ‐subgraph problems

Daniela Scherer dos Santos, Kathrin Klamroth, Pedro Martins, Luís Paquete

International Transactions in Operational Research · 2026-11 · 33 (6) · 3800-3824

DOI: 10.1111/itor.70184 ↗

Kurz gefasst

Fachartikel in der Zeitschrift International Transactions in Operational Research, online erschienen am 11.04.2026. Verfasst von Daniela Scherer dos Santos und 3 weiteren Autor:innen. Die Arbeit nennt 44 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundação para a Ciência e a Tecnologia, European Cooperation in Science and Technology.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Given an undirected graph , a quasi‐clique is a subgraph of with density at least . Two optimisation problems can be defined for quasi‐cliques: the maximum quasi‐clique (MQC) problem, which finds a quasi‐clique with maximum vertex cardinality, and the densest ‐subgraph (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‐life applications. To address this issue, we propose two flow‐based and an Miller–Tucher–Zemlin‐based connectedness constraint for integration into existing mixed‐integer 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‐clique connectedness. Experimental results demonstrate that our constraints are competitive, making them valuable for practical applications requiring connectedness.

Förderung

  • Fundação para a Ciência e a Tecnologia
  • European Cooperation in Science and Technology

Zitieren

APA

Santos, D. S. D., Klamroth, K., Martins, P., & Paquete, L. (2026). Ensuring connectedness for the maximum quasi‐clique and densest k ‐subgraph problems. International Transactions in Operational Research, 33(6), 3800-3824. https://doi.org/10.1111/itor.70184

Vancouver

Santos DSD, Klamroth K, Martins P, Paquete L. Ensuring connectedness for the maximum quasi‐clique and densest k ‐subgraph problems. International Transactions in Operational Research. 2026;33(6):3800-3824. doi:10.1111/itor.70184

BibTeX
@article{Santos2026,
  author = {Santos, Daniela Scherer dos and Klamroth, Kathrin and Martins, Pedro and Paquete, Luís},
  title = {Ensuring connectedness for the maximum quasi‐clique and densest k ‐subgraph problems},
  journal = {International Transactions in Operational Research},
  year = {2026},
  volume = {33},
  number = {6},
  pages = {3800--3824},
  doi = {10.1111/itor.70184}
}
Kostenlos starten →