Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: cubic graphs

Sortuj według:

Ogranicz wyniki do:

Approximate solutions of Happynet on cubic graphs

Giannakos A., Pottie O.

Foundations of Computing and Decision Sciences

2006

Vol. 31, No. 3-4

233-241

The HAPPYNET problem is defined as follows : Given a undirected simple graph G with integer weights wvu on its edges vu 6 E(G), find a function s : V(G] → { — 1,1} such that ∀νV(G), v is happy in G, i.e. such that . 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) HAPPYNET is as difficult as for arbitrary graphs. A ρ-approximate solution to a HAPPYNET instance of size n can be defined for 0 le ρ le 1 as a natural extension of the solution function, with at least pn happy vertices. In this paper, we present a polynomial-time algorithm that finds a ρ-approximate solution for the HAPPYNET problem on cubic graphs, with ρ 3/4 .

A note on the vertex-distinguishing index for some cubic graphs

Taczuk K., Woźniak M.

Opuscula Mathematica

2004

Vol. 24, no. 2

223-229

The vertex-distinguishing index of a graph G (vdi (G)) is the minimum number of colours required to colour properly the edges of a graph in such a way that any two vertices are incident with different sets of colours. We consider this parameter for some families of cubic graphs.