• 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 - Request a copy

A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem

Afif, Mohamed; Likas, Aris; Paschos, Vangelis (1995), A natural model and a parallel algorithm for approximately solving the maximum weighted independent set problem, Chaos, Solitons and Fractals, 5, 5, p. 739-746. http://dx.doi.org/10.1016/0960-0779(94)00175-P

Type
Article accepté pour publication ou publié
Date
1995
Journal name
Chaos, Solitons and Fractals
Volume
5
Number
5
Publisher
Elsevier
Pages
739-746
Publication identifier
http://dx.doi.org/10.1016/0960-0779(94)00175-P
Metadata
Show full item record
Author(s)
Afif, Mohamed
Likas, Aris
Paschos, Vangelis
Abstract (EN)
A dynamical model based upon a physical metaphor is described, and a parallel algorithm inspired from the model is developed for approximately solving maximum weight independent set problem. Our model treats an independent set as an attraction game, where vertices of the graph are considered as still bodies and edges as cells attracted by the still bodies corresponding to its extremities. In addition, we discuss how, by using an analogous model, an approximation algorithm can be developed for the minimum set covering problem.
Subjects / Keywords
Algorithmes

Related items

Showing items related by title and author.

  • Thumbnail
    Average-case complexity of a branch-and-bound algorithm for maximum independent set, under the $\mathcal{G}(n,p)$ random model 
    Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper
  • Thumbnail
    A (°/2)-approximation algorithm for the maximum independent set problem 
    Paschos, Vangelis (1992) Article accepté pour publication ou publié
  • Thumbnail
    A priori optimization for the probabilistic maximum independent set problem 
    Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié
  • Thumbnail
    A generalization of König-Egervary graphs and heuristics for maximum independent set problem with improved approximation ratios 
    Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
  • Thumbnail
    On-line models and algorithms for max independent set 
    Paschos, Vangelis; Escoffier, Bruno (2006) 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