Efficient computation of a near-maximum independent set over evolving graphs

Weiguo Zheng, Qichen Wang, Jeffrey Xu Yu, Hong Cheng, Lei Zou

Research output: Chapter in book/report/conference proceedingConference contributionpeer-review

7 Citations (Scopus)

Abstract

Most existing algorithms computing the maximum independent set (MIS) or independent set (IS) are designed for handling static graphs, which may not be practicable as many networks are dynamically evolving over time. In this paper, we study the MIS/IS problem in evolving graphs by considering graph update operations: vertex/edge addition and vertex/edge deletion. Instead of computing the MIS/IS of the updated graph from scratch, we propose a baseline algorithm that finds the MIS/IS at time t i+1 based on the MIS/IS at time ti. Due to the hardness of computing an exact MIS, we develop an efficient constant-Time algorithm LSTwo to return a high-quality (large-size) independent set. Then we design a lazy search algorithm which produces higher-quality independent sets. To improve the time efficiency further, we devise the conditional besieging and k-petal based methods to reduce the search space. Extensive experimental studies over large-scale graphs confirm the effectiveness and efficiency of our proposed algorithms.

Original languageEnglish
Title of host publicationProceedings - IEEE 34th International Conference on Data Engineering, ICDE 2018
PublisherIEEE
Pages869-880
Number of pages12
ISBN (Electronic)9781538655207
ISBN (Print)9781538655214
DOIs
Publication statusPublished - 16 Apr 2018
Event34th IEEE International Conference on Data Engineering, ICDE 2018 - Paris, France
Duration: 16 Apr 201819 Apr 2018
https://ieeexplore.ieee.org/xpl/conhome/8476188/proceeding

Publication series

NameProceedings - IEEE International Conference on Data Engineering (ICDE)
ISSN (Print)1063-6382
ISSN (Electronic)2375-026X

Conference

Conference34th IEEE International Conference on Data Engineering, ICDE 2018
Country/TerritoryFrance
CityParis
Period16/04/1819/04/18
Internet address

Scopus Subject Areas

  • Information Systems
  • Information Systems and Management
  • Hardware and Architecture

User-Defined Keywords

  • Evolving graph
  • greedy algorithm
  • independent set
  • maximum independent set

Fingerprint

Dive into the research topics of 'Efficient computation of a near-maximum independent set over evolving graphs'. Together they form a unique fingerprint.

Cite this