Wyszukiwarka
Abstrakt
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
- Kategoria:
- Publikacja w czasopiśmie
- Typ:
- 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 - Język:
- angielski
- Rok wydania:
- 2011
- 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
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 105 razy