• français
    • English
  • français 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Exact and superpolynomial approximation algorithms for the densest k-subgraph problem

Thumbnail
Date
2017
Link to item file
https://hal.inria.fr/hal-01539561
Dewey
Recherche opérationnelle
Sujet
combinatorial optimization; dense subgraphs; exact and parameterized algorithms; superpolynomial approximation algorithms
Journal issue
European Journal of Operational Research
Volume
262
Number
3
Publication date
11-2017
Article pages
894-903
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejor.2017.04.034
URI
https://basepub.dauphine.fr/handle/123456789/20823
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Bourgeois, Nicolas
Giannakos, Aristotelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lucarelli, Giorgio
Milis, Ioannis
Paschos, Vangelis
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Article accepté pour publication ou publié
Abstract (EN)
The 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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.