GreedyMAX-type Algorithms for the Maximum Independent Set Problem - Publication - Bridge of Knowledge

Search

GreedyMAX-type Algorithms for the Maximum Independent Set Problem

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.

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 64 times

Recommended for you

Meta Tags