A Natural Model and a Parallel Algorithm for Approximately Solving the Maximum Weighted Independent Set Problem

dc.contributor.author	Afif, M.	en
dc.contributor.author	Likas, A.	en
dc.contributor.author	Paschos, V. T.	en
dc.date.accessioned	2015-11-24T17:01:09Z
dc.date.available	2015-11-24T17:01:09Z
dc.identifier.issn	0960-0779	-
dc.identifier.uri	https://olympias.lib.uoi.gr/jspui/handle/123456789/10878
dc.rights	Default Licence	-
dc.title	A Natural Model and a Parallel Algorithm for Approximately Solving the Maximum Weighted Independent Set Problem	en
heal.abstract	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.	en
heal.access	campus	-
heal.fullTextAvailability	TRUE	-
heal.journalName	Chaos Solitons & Fractals	en
heal.journalType	peer reviewed	-
heal.language	en	-
heal.publicationDate	1995	-
heal.recordProvider	Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής	el
heal.type	journalArticle	-
heal.type.el	Άρθρο Περιοδικού	el
heal.type.en	Journal article	en

Αρχεία

Προβολή: 1 - 1 of 1