GreedyMAX-type Algorithms for the Maximum Independent Set Problem - Publikacja - MOST Wiedzy


GreedyMAX-type Algorithms for the Maximum Independent Set Problem


A maximum independent set problem for a simple graph G = (V,E) is to find the largest subset of pairwise nonadjacent vertices. The problem is known to be NP-hard and it is also hard to approximate. Within this article we introduce a non-negative integer valued functionp defined on the vertex set V(G) and called a potential function of agraph G, while P(G) = max{vinV(G)| p(v)} is called a potential of G. For any graph P(G) <= D(G), where D(G) is the maximum degree of G.Moreover, D(G)-P(G) may be arbitrarily large. A potential of a vertexlets us get a closer insight into the properties of its neighborhoodwhich leads to the definition of the family of GreedyMAX-type algorithms having the classical GreedyMAX algorithm as their origin. We establish a lower bound 1/(P + 1) for the performance ratio of GreedyMAX-type algorithms which favorably compares with the bound 1/(D + 1) known to hold for GreedyMAX. The cardinality of an independent set generated by any GreedyMAX-type algorithm is at least sum_{vin V(G)} (p(v)+1)−1, which strengthens the bounds of Tur´an and Caro-Wei stated in terms of vertex degrees.

Cytuj jako

Pełna treść

pełna treść publikacji nie jest dostępna w portalu

Słowa kluczowe

Informacje szczegółowe

Publikacja w czasopiśmie
artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
Opublikowano w:
LECTURE NOTES IN COMPUTER SCIENCE nr 6543, strony 146 - 156,
ISSN: 0302-9743
Rok wydania:
Opis bibliograficzny:
Borowiecki P., Goering F.: GreedyMAX-type Algorithms for the Maximum Independent Set Problem// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6543., (2011), s.146-156
Politechnika Gdańska

wyświetlono 33 razy

Publikacje, które mogą cię zainteresować

Meta Tagi