
Approximate solutions of Happynet on cubic graphs
Pottié, Olivier; Giannakos, Aristotelis (2006), Approximate solutions of Happynet on cubic graphs, Foundations of Computing and Decision Sciences, 31, 3-4, p. 233-242
View/ Open
Type
Article accepté pour publication ou publiéDate
2006Journal name
Foundations of Computing and Decision SciencesVolume
31Number
3-4Publisher
Institute of Computing Science
Pages
233-242
Metadata
Show full item recordAbstract (EN)
The HAPPYNET problem is defined as follows : Given an undirected simple graph G with integer weights wvu on its edges vu ∈ E(G), find a function s : V(G) → {-1, 1} such that ∀v ∈ V (G), v is happy in G, i.e. such that ∑u∈Γs(v)s(u) wvu ≥ 0. It is easy to see [3] that HAPPYNET has always a solution, no matter what the input is. However, no polynomial algorithm is known for this problem, which is complete for the class PLS (see [4] for a definition). Parberry et al. have shown in [7] that in the case of cubic graphs (i.e. of maximum degree 3) is as difficult as for arbitrary graphs. A ρ-approximate solution to a HAPPYNET instance of size n can be defined for 0 ≤ ρ ≤ 1 as a natural extension of the solution function, with at least ρn happy vertices. In this paper, we present a polynomial-time algorithm that finds a ρ-approximate solution for the HAPPYNET problem on cubic graphs, with ρ ≥ ¾.Subjects / Keywords
Polynomial algorithm; GraphRelated items
Showing items related by title and author.
-
Bourgeois, Nicolas; Giannakos, Aristotelis; Lucarelli, Giorgio; Milis, Ioannis; Paschos, Vangelis; Pottié, Olivier (2012) Article accepté pour publication ou publié
-
Pottié, Olivier; Paschos, Vangelis; Milis, Ioannis; Lucarelli, Giorgio; Giannakos, Aristotelis; Bourgeois, Nicolas (2010) Communication / Conférence
-
Paschos, Vangelis; Giannakos, Aristotelis; Pottié, Olivier (2008) Chapitre d'ouvrage
-
Kheffache, Rezika; Giannakos, Aristotelis (2012-12) Document de travail / Working paper
-
Gastineau, Nicolas; Togni, Olivier (2019) Article accepté pour publication ou publié