Show simple item record

Exact and approximation algorithms for densest k-subgraph

dc.contributor.authorLucarelli, Giorgio
HAL ID: 5944
ORCID: 0000-0001-7368-355X
dc.contributor.authorMilis, Ioannis
dc.contributor.authorGiannakos, Aristotelis
dc.contributor.authorPaschos, Vangelis
dc.contributor.authorBourgeois, Nicolas
dc.date.accessioned2012-07-11T15:06:58Z
dc.date.available2012-07-11T15:06:58Z
dc.date.issued2013
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/9732
dc.language.isoenen
dc.subjectapproximation algorithms
dc.subjectalgorithms
dc.subject.ddc003en
dc.titleExact and approximation algorithms for densest k-subgraph
dc.typeCommunication / Conférence
dc.description.abstractenThe 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.
dc.identifier.citationpages348
dc.relation.ispartoftitleWALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings
dc.relation.ispartofeditorTokuyama, Takeshi
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2013
dc.identifier.urlsitehttps://hal.archives-ouvertes.fr/hal-00874586
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-36064-0
dc.relation.confcountryINDIA
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2016-11-25T17:46:18Z


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record