An exact algorithm to find a maximum weight clique in a weighted undirected graph
Abstract We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficien...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2024-04-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-024-59689-x |
| _version_ | 1797199501193117696 |
|---|---|
| author | Kati Rozman An Ghysels Dušanka Janežič Janez Konc |
| author_facet | Kati Rozman An Ghysels Dušanka Janežič Janez Konc |
| author_sort | Kati Rozman |
| collection | DOAJ |
| description | Abstract We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery. |
| first_indexed | 2024-04-24T07:16:45Z |
| format | Article |
| id | doaj.art-d470508c32c24c47bb9b0a0f7716bf64 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-04-24T07:16:45Z |
| publishDate | 2024-04-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-d470508c32c24c47bb9b0a0f7716bf642024-04-21T11:17:12ZengNature PortfolioScientific Reports2045-23222024-04-0114111110.1038/s41598-024-59689-xAn exact algorithm to find a maximum weight clique in a weighted undirected graphKati Rozman0An Ghysels1Dušanka Janežič2Janez Konc3Faculty of Mathematics, Natural Sciences and Information Technologies, University of PrimorskaIBiTech – BioMMedA Group, Ghent UniversityFaculty of Mathematics, Natural Sciences and Information Technologies, University of PrimorskaFaculty of Mathematics, Natural Sciences and Information Technologies, University of PrimorskaAbstract We introduce a new algorithm MaxCliqueWeight for identifying a maximum weight clique in a weighted graph, and its variant MaxCliqueDynWeight with dynamically varying bounds. This algorithm uses an efficient branch-and-bound approach with a new weighted graph coloring algorithm that efficiently determines upper weight bounds for a maximum weighted clique in a graph. We evaluate our algorithm on random weighted graphs with node counts up to 10,000 and on standard DIMACS benchmark graphs used in a variety of research areas. Our findings reveal a remarkable improvement in computational speed when compared to existing algorithms, particularly evident in the case of high-density random graphs and DIMACS graphs, where our newly developed algorithm outperforms existing alternatives by several orders of magnitude. The newly developed algorithm and its variant are freely available to the broader research community at http://insilab.org/maxcliqueweight , paving the way for transformative applications in various research areas, including drug discovery.https://doi.org/10.1038/s41598-024-59689-x |
| spellingShingle | Kati Rozman An Ghysels Dušanka Janežič Janez Konc An exact algorithm to find a maximum weight clique in a weighted undirected graph Scientific Reports |
| title | An exact algorithm to find a maximum weight clique in a weighted undirected graph |
| title_full | An exact algorithm to find a maximum weight clique in a weighted undirected graph |
| title_fullStr | An exact algorithm to find a maximum weight clique in a weighted undirected graph |
| title_full_unstemmed | An exact algorithm to find a maximum weight clique in a weighted undirected graph |
| title_short | An exact algorithm to find a maximum weight clique in a weighted undirected graph |
| title_sort | exact algorithm to find a maximum weight clique in a weighted undirected graph |
| url | https://doi.org/10.1038/s41598-024-59689-x |
| work_keys_str_mv | AT katirozman anexactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT anghysels anexactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT dusankajanezic anexactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT janezkonc anexactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT katirozman exactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT anghysels exactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT dusankajanezic exactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph AT janezkonc exactalgorithmtofindamaximumweightcliqueinaweightedundirectedgraph |