Search
Abstract
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.
Authors (2)
Cite as
Full text
full text is not available in portal
Keywords
Details
- Category:
- Articles
- Type:
- artykuły w czasopismach recenzowanych i innych wydawnictwach ciągłych
- Published in:
-
LECTURE NOTES IN COMPUTER SCIENCE
no. 6543,
pages 146 - 156,
ISSN: 0302-9743 - Language:
- English
- Publication year:
- 2011
- Bibliographic description:
- Borowiecki P., Goering F.: GreedyMAX-type Algorithms for the Maximum Independent Set Problem// LECTURE NOTES IN COMPUTER SCIENCE. -Vol. 6543., (2011), s.146-156
- Verified by:
- Gdańsk University of Technology
seen 101 times