Approximating the Minimum Hub Cover Problem on Planar Graphs

We study an approximation algorithm with a performance guarantee to solve a new NP-hard optimization problem on planar graphs. The problem, which is referred to as the minimum hub cover problem, has recently been introduced to the literature to improve query processing over large graph databases. Planar graphs also arise in various graph query processing … Read more