On solving the densest k-subgraph problem on large graphs

Research output: Contribution to journalArticleScientificpeer-review

Abstract

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.
Original languageEnglish
JournalOptimization Methods and Software
DOIs
Publication statusPublished - 2019

Fingerprint

Subgraph
Graph in graph theory
Update
Coordinate Descent
Updating
Iteration
Vertex of a graph

Cite this

@article{e0b59ba3932c47a8863650983e6e8247,
title = "On solving the densest k-subgraph problem on large graphs",
abstract = "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.",
author = "Renata Sotirov",
year = "2019",
doi = "https://doi.org/10.1080/10556788.2019.1595620",
language = "English",
journal = "Optimization Methods and Software",
issn = "1055-6788",
publisher = "Taylor and Francis Ltd.",

}

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

In: Optimization Methods and Software, 2019.

Research output: Contribution to journalArticleScientificpeer-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 -