Show simple item record

dc.contributor.authorBourgeois, Nicolas
dc.contributor.authorGiannakos, Aristotelis
dc.contributor.authorLucarelli, Giorgio
dc.contributor.authorMilis, Ioannis
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2020-06-03T14:54:05Z
dc.date.available2020-06-03T14:54:05Z
dc.date.issued2017
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20823
dc.language.isoenen
dc.subjectcombinatorial optimizationen
dc.subjectdense subgraphsen
dc.subjectexact and parameterized algorithmsen
dc.subjectsuperpolynomial approximation algorithmsen
dc.subject.ddc003en
dc.titleExact and superpolynomial approximation algorithms for the densest k-subgraph problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe densest k-subgraph problem is a generalization of the maximum clique problem, in which we are given a graph and a positive integer k, and we search among all the subsets of k vertices of the input graph for the subset which induces the maximum number of edges. densest k-subgraph is a well known optimization problem with various applications as, for example, in the design of public encryption schemes, the evaluation of certain financial derivatives, the identification of communities with similar characteristics, etc. In this paper, we first present algorithms for finding exact solutions for densest k-subgraph which improve upon the standard exponential time complexity of an exhaustive enumeration by creating a link between the computation of an optimum for this problem to the computation of other graph-parameters such as dominating set, vertex cover, longest path, etc. An FPT algorithm is also proposed which considers as a parameter the size of the minimum vertex cover. Finally, we present several approximation algorithms which run in moderately exponential or parameterized time, describing trade-offs between complexity and approximability. In contrast with most of the algorithms in the bibliography, our algorithms need only polynomial space.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol262en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2017-11
dc.relation.isversionofjnlpages894-903en
dc.relation.isversionofdoi10.1016/j.ejor.2017.04.034en
dc.identifier.urlsitehttps://hal.inria.fr/hal-01539561en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-06-03T14:51:40Z
hal.person.labIds
hal.person.labIds989
hal.person.labIds
hal.person.labIds
hal.person.labIds989


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