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
1995Journal name
Chaos, Solitons and FractalsVolume
5Number
5Publisher
Elsevier
Pages
739-746
Publication identifier
Metadata
Show full item recordAbstract (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
AlgorithmesRelated items
Showing items related by title and author.
-
Bourgeois, N.; Catellier, Rémi; Denat, T.; Paschos, Vangelis (2015) Document de travail / Working paper
-
Paschos, Vangelis (1992) Article accepté pour publication ou publié
-
Paschos, Vangelis; Demange, Marc (1997) Article accepté pour publication ou publié
-
Murat, Cécile; Paschos, Vangelis (2002) Article accepté pour publication ou publié
-
Paschos, Vangelis; Escoffier, Bruno (2006) Article accepté pour publication ou publié