Maximum Independent Set ( MaxIS%DIFDELCMD < }%%% ) problem is a fundamental  problem in graph theory, which is NP-hard . Since the underlying graphs  are always changing in numerous applications, computing a MaxIS over dynamic graphs has received increasing attention in recent years. Due to the intractability to compute an exact MaxIS or its good approximation over dynamic graphs , this paper studies the problem to maintain a high-quality independent set, which is an approximation of the MaxIS , over dynamic graphs\ie . A framework based on swap operations for resolving this problem is presented and two concrete update algorithms based on one-swappable vertices and two-swappble vertex pairs are designed. Both algorithms can compute high-quality independent sets over dynamic graphs with O(\Delta^3) time for general graphs and with O( 1 ) time for bounded-degree graphs. Moreover, the lower bound of the size of the solution maintained by our algorithms is derived if there is no swappable vertex in it. Then the algorithms are extended under\textit{semi-external setting to maintained a high-quality independent set with limited memory consumption . Extensive experiments are conducted over real graphs to confirm the effectiveness and efficiency of the proposed methods .
 %DIFDELCMD < }%%% Computing a maximum independent set (MaxIS) is a fundamental NP-hard problem in graph theory, which has important applications in a wide range of areas such as social network analysis, graphical information systems and coding theory . Since the underlying graphs of numerous applications are always changing continuously, the problem of maintaining a MaxIS over dynamic graphs has received increasing attention in recent years. Due to the intractability of maintaining an exact MaxIS , this paper studies the problem of maintaining an approximate MaxIS over fully dynamic graphs, where 4 graph update operations are allowed\ie, adding or deleting a vertex or an edge. Based on swap operation, we present a novel framework for maintaining an approximate maximum independent set which contains no k-swaps and make a deep analysis of performance ratio achieved by it . We implement a dynamic (\frac{\Delta 1 \textit{ )-approximate algorithm and a more effective algorithm based on one-swap vertex and two-swap vertex set respectively and make a further analysis of their performance based on Power-Law Random graph model . Extensive experiments are conducted over real graphs to confirm the effectiveness and efficiency of the proposed algorithms .
D
Maximum Independent Set (
D
MaxIS
R
) problem
Computing a maximum independent set (MaxIS)
A
NP-hard
R
is NP-hard
has important applications in a wide range of areas such as social network analysis, graphical information systems and coding theory
A
of numerous applications
D
in numerous applications, computing a
R
MaxIS
continuously, the problem of maintaining a MaxIS
R
to compute
of maintaining
D
or its good approximation over dynamic graphs
R
to maintain a high-quality independent set, which is an approximation of the MaxIS , over dynamic graphs
of maintaining an approximate MaxIS over fully dynamic graphs, where 4 graph update operations are allowed
A
, adding or deleting a vertex or an edge. Based on swap operation, we present a novel framework for maintaining an approximate maximum independent set which contains no k-swaps and make a deep analysis of performance ratio achieved by it
R
A framework based on swap operations for resolving this problem is presented and two concrete update algorithms based on one-swappable vertices and two-swappble vertex pairs are designed. Both algorithms can compute high-quality independent sets over dynamic graphs with O(\Delta^3) time for general graphs and with O(
We implement a dynamic (\frac{\Delta
D
) time for bounded-degree graphs. Moreover, the lower bound of the size of the solution maintained by our algorithms is derived if there is no swappable vertex in it. Then the algorithms are extended under
D
semi-external
R
setting to maintained a high-quality independent set with limited memory consumption
)-approximate algorithm and a more effective algorithm based on one-swap vertex and two-swap vertex set respectively and make a further analysis of their performance based on Power-Law Random graph model
R
methods
algorithms