• 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 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

Type
Communication / Conférence
External document link
https://hal.archives-ouvertes.fr/hal-00874586
Date
2013
Conference country
INDIA
Book title
WALCOM: Algorithms and Computation7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings
Book author
Tokuyama, Takeshi
Publisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-36064-0
Pages
348
Metadata
Show full item record
Author(s)
Lucarelli, Giorgio cc
Milis, Ioannis
Giannakos, Aristotelis
Paschos, Vangelis
Bourgeois, Nicolas
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 / Keywords
approximation algorithms; algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Exact and superpolynomial approximation algorithms for the densest k-subgraph problem 
    Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2017) Article accepté pour publication ou publié
  • 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
    Greedy algorithms for on-line set-covering 
    Bourgeois, Nicolas; Ausiello, Giorgio; Paschos, Vangelis; Giannakos, Aristotelis (2009) Article accepté pour publication ou publié
  • Thumbnail
    Approximating the max edge-coloring problem 
    Bourgeois, Nicolas; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis (2010) Article accepté pour publication ou publié
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