.png){kind=icon}
.png){kind=icon}
Return
Approximation Algorithm for the Minimum Hub Cover Set Problem
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2022.3173615.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A subset S subset of V of vertices of an undirected graph G = (V, E) is a hub cover when for each edge (u, v) is an element of E, at least one of its endpoints belongs to S, or there exists a vertex r is an element of S that is a neighbor of both u and v. The problem of computing a minimum hub cover set in arbitrary graphs is NP-hard. This problem has applications for indexing large databases. This paper proposes psi-MHC, the first approximation algorithm for the minimum hub cover set in arbitrary graphs to the best of our knowledge. The approximation ratio of this algorithm is In mu, where mu is upper bounded by min{1/2(Delta + 1)(2), vertical bar E vertical bar} and Delta is the degree of G. The execution time of psi-MHC is O((Delta + 1)vertical bar E vertical bar + vertical bar S vertical bar vertical bar E vertical bar). Experimental results show that klf-MHC far outperforms the theoretical approximation ratio for the input graph instances.
Keywords:
Approximation algorithms
heuristics
minimum hub cover set
optimization
Journal
IF:
3.6
Papers:
9.8W
Citations:
29.4W
View more organizations