Finding k most influential edges on flow graphs

作者：

Highlights：

• We propose two graph problems: the k Most Beneficial New Edges (kMBNE), and the k Most Lethal Existing Edges (kMLEE).

• First, we prove that kMBNE and kMLEE are inapproximable. It is hard to find even an approximate solution (with constant approximation ratio), let alone find the exact solution.

• For both kMBNE and kMLEE, we develop polynomial-time heuristic algorithms that give high-quality solutions on real flow graphs. Moreover, we propose several pruning and optimization techniques to speedup our proposed algorithms.

摘要

Highlights•We propose two graph problems: the k Most Beneficial New Edges (kMBNE), and the k Most Lethal Existing Edges (kMLEE).•First, we prove that kMBNE and kMLEE are inapproximable. It is hard to find even an approximate solution (with constant approximation ratio), let alone find the exact solution.•For both kMBNE and kMLEE, we develop polynomial-time heuristic algorithms that give high-quality solutions on real flow graphs. Moreover, we propose several pruning and optimization techniques to speedup our proposed algorithms.

论文关键词：Graph

论文评审过程：Received 7 July 2015, Revised 17 November 2016, Accepted 1 December 2016, Available online 8 December 2016, Version of Record 25 December 2016.

论文官网地址：https://doi.org/10.1016/j.is.2016.12.002