• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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

Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017), Exact and superpolynomial approximation algorithms for the densest k-subgraph problem, European Journal of Operational Research, 262, 3, p. 894-903. 10.1016/j.ejor.2017.04.034

Type
Article accepté pour publication ou publié
External document link
https://hal.inria.fr/hal-01539561
Date
2017
Journal name
European Journal of Operational Research
Volume
262
Number
3
Publisher
Elsevier
Pages
894-903
Publication identifier
10.1016/j.ejor.2017.04.034
Metadata
Show full item record
Author(s)
Bourgeois, Nicolas

Giannakos, Aristotelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Lucarelli, Giorgio cc

Milis, Ioannis

Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.
Subjects / Keywords
combinatorial optimization; dense subgraphs; exact and parameterized algorithms; superpolynomial approximation algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Exact and approximation algorithms for densest k-subgraph 
    Lucarelli, Giorgio; Milis, Ioannis; Giannakos, Aristotelis; Paschos, Vangelis; Bourgeois, Nicolas (2013) Communication / Conférence
  • Thumbnail
    The max quasi-independent set problem 
    Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié
  • Thumbnail
    The Max Quasi-Independent Set Problem 
    Pottié, Olivier; Paschos, Vangelis; Milis, Ioannis; Lucarelli, Giorgio; Giannakos, Aristotelis; Bourgeois, Nicolas (2010) Communication / Conférence
  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2009) Communication / Conférence
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo