Finding k most influential edges on flow graphs

Petrie Wong, Cliz Sun, Eric Lo, Man Lung Yiu, Xiaowei Wu, Zhichao Zhao, T. H. Hubert Chan, Ben Kao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

12 Citations (Scopus)


Specifically, this problem aims to find which k edges would have the largest impact on a maximum flow query on a network. This problem has important applications in areas like social network and network planning. We show the inapproximability of the problems and present our heuristic algorithms. Experimental evaluations are carried out on real datasets and results show that our algorithms are scalable and return high quality solutions.
Original languageEnglish
Pages (from-to)93-105
Number of pages13
JournalInformation Systems
Publication statusPublished - 1 Apr 2017


  • Graph

ASJC Scopus subject areas

  • Software
  • Information Systems
  • Hardware and Architecture


Dive into the research topics of 'Finding k most influential edges on flow graphs'. Together they form a unique fingerprint.

Cite this