Exact and approximation algorithms for densest k-subgraph

Lucarelli, Giorgio; Milis, Ioannis; Giannakos, Aristotelis; Paschos, Vangelis; Bourgeois, Nicolas

Lucarelli, Giorgio; Milis, Ioannis; Giannakos, Aristotelis; Paschos, Vangelis; Bourgeois, Nicolas (2013), Exact and approximation algorithms for densest k-subgraph, dans Tokuyama, Takeshi, WALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, Springer : Berlin Heidelberg, p. 348

Type

Communication / Conférence

Lien vers un document non conservé dans cette base

https://hal.archives-ouvertes.fr/hal-00874586

Date

2013

Pays du colloque

INDIA

Titre de l'ouvrage

WALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings

Auteurs de l’ouvrage

Tokuyama, Takeshi

Éditeur

Springer

Ville d’édition

Berlin Heidelberg

Isbn

978-3-642-36064-0

Pages

348

Métadonnées

Afficher la notice complète

Auteur(s)

Lucarelli, Giorgio

Milis, Ioannis
Giannakos, Aristotelis
Paschos, Vangelis
Bourgeois, Nicolas

Résumé (EN)

The densest k-subgraph problem is a generalization of the maximum clique problem, inwhich we are given a graph G and a positive integer k , and we search among the subsets of kvertices of G one inducing a maximum number of edges. In this paper, we present algorithmsfor finding exact solutions of densest k-subgraph improving the standard exponential timecomplexity of O ∗(2 n) and using polynomial space. Two FPT algorithms are also proposed;the first considers as parameter the tree width of the input graph and uses exponential space,while the second is parameterized by the size of the minimum vertex cover and uses polynomialspace. Finally, we propose several approximation algorithms running in moderately exponentialor parameterized time.

Mots-clés

approximation algorithms; algorithms