kth.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An Implicit Enumeration Approach for Maximum Ratio Clique Relaxations
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Numerical Analysis, Optimization and Systems Theory.ORCID iD: 0009-0006-5926-0781
Wm. Michael Barnes'64 Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas, USA.
Wm. Michael Barnes'64 Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas, USA.
Wm. Michael Barnes'64 Department of Industrial and Systems Engineering, Texas A&M University, College Station, Texas, USA.
Show others and affiliations
2025 (English)In: Networks, ISSN 0028-3045, E-ISSN 1097-0037Article in journal (Refereed) Epub ahead of print
Abstract [en]

This article proposes an implicit enumeration approach to solve the maximum ratio (Formula presented.) -plex and the maximum ratio (Formula presented.) -defective clique problems. The approach is inspired by the classical Bron-Kerbosch algorithm for enumerating all maximal cliques in a graph, which is extended to enumerating structures that are hereditary on induced subgraphs. Such structures include (Formula presented.) -plexes and (Formula presented.) -defective cliques, among many others. The performance of the proposed approach is compared with that of the methods based on mixed integer linear programming (MILP), binary search, and Newton's iteration through numerical experiments on randomly generated and real-life network instances.

Place, publisher, year, edition, pages
Wiley , 2025.
Keywords [en]
clique relaxations, maximum ratio s-plex, network analysis, s-defective clique, strong s-plex
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:kth:diva-368549DOI: 10.1002/net.22288ISI: 001508006700001Scopus ID: 2-s2.0-105008213357OAI: oai:DiVA.org:kth-368549DiVA, id: diva2:1990390
Note

QC 20250820

Available from: 2025-08-20 Created: 2025-08-20 Last updated: 2025-08-20Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Blokhin, Yehor

Search in DiVA

By author/editor
Blokhin, Yehor
By organisation
Numerical Analysis, Optimization and Systems Theory
In the same journal
Networks
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 20 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf