Exact and approximation algorithms for densest k-subgraph
Lucarelli, Giorgio; Milis, Ioannis; Giannakos, Aristotelis; Paschos, Vangelis; Bourgeois, Nicolas (2013), Exact and approximation algorithms for densest k-subgraph, in Tokuyama, Takeshi, WALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings, Springer : Berlin Heidelberg, p. 348
TypeCommunication / Conférence
External document linkhttps://hal.archives-ouvertes.fr/hal-00874586
Book titleWALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings
Book authorTokuyama, Takeshi
MetadataShow full item record
Abstract (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.
Subjects / Keywordsapproximation algorithms; algorithms
Showing items related by title and author.
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié