Paper Info
Title
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 function p defined on the vertex set V (G) and called a potential function of a graph G, while P(G) = maxv∈V(G) p(v) is called a potential of G. For any graph P(G) ≤ Δ(G), where Δ(G) is the maximum degree of G. Moreover, Δ(G) - P(G) may be arbitrarily large. A potential of a vertex lets us get a closer insight into the properties of its neighborhood which 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/(Δ + 1) known to hold for GreedyMAX. The cardinality of an independent set generated by any GreedyMAX-type algorithm is at least Σv∈V(G)(p(v)+1)-1, which strengthens the bounds of Turáan and Caro-Wei stated in terms of vertex degrees.
Year
DOI
Venue
2011
10.1007/978-3-642-18381-2_12
SOFSEM
Keywords
Field
DocType
classical greedymax algorithm,graph p,vertex degree,potential function,maximum independent set problem,simple graph,graph g,independent set,greedymax-type algorithm,pairwise nonadjacent vertex,maximum independent set,maximum degree,stable set,value function,lower bound
Discrete mathematics,Combinatorics,Bound graph,Vertex (geometry),Graph power,Upper and lower bounds,Algorithm,Neighbourhood (graph theory),Independent set,Degree (graph theory),Mathematics,Maximal independent set
Conference
Volume
ISSN
Citations 
6543
0302-9743
3
PageRank 
References 
Authors
0.42
18
2
Name
Order
Citations
PageRank
Piotr Borowiecki1438.12
Frank Göring2539.00