### Abstract

Original language | English |
---|---|

Journal | Optimization Methods and Software |

DOIs | |

Publication status | Published - 2019 |

### Fingerprint

### Cite this

}

**On solving the densest k-subgraph problem on large graphs.** / Sotirov, Renata.

Research output: Contribution to journal › Article › Scientific › peer-review

TY - JOUR

T1 - On solving the densest k-subgraph problem on large graphs

AU - Sotirov, Renata

PY - 2019

Y1 - 2019

N2 - The densest k-subgraph problem is the problem of finding a k-vertex subgraph of a graph with the maximum number of edges. In order to solve large instances of the densest k-subgraph problem, we introduce two algorithms that are based on the random coordinate descent approach. Although it is common use to update at most two random coordinates simultaneously in each iteration of an algorithm, our algorithms may simultaneously update many coordinates. We show the benefit of updating more than two coordinates simultaneously for solving the densest k-subgraph problem, and solve large problem instances with up to 2^{15} vertices.

AB - The densest k-subgraph problem is the problem of finding a k-vertex subgraph of a graph with the maximum number of edges. In order to solve large instances of the densest k-subgraph problem, we introduce two algorithms that are based on the random coordinate descent approach. Although it is common use to update at most two random coordinates simultaneously in each iteration of an algorithm, our algorithms may simultaneously update many coordinates. We show the benefit of updating more than two coordinates simultaneously for solving the densest k-subgraph problem, and solve large problem instances with up to 2^{15} vertices.

U2 - https://doi.org/10.1080/10556788.2019.1595620

DO - https://doi.org/10.1080/10556788.2019.1595620

M3 - Article

JO - Optimization Methods and Software

JF - Optimization Methods and Software

SN - 1055-6788

ER -