Minimum hub cover problem: solution methods and applications

Official URL: http://risc01.sabanciuniv.edu/record=b1589810 (Table of Contents)

The minimum hub cover is a new NP-hard optimization problem that has been recently introduced to the literature in the context of graph query processing on graph databases. The problem has been introduced as a new graph representation model to expedite graph queries. With this representation, a graph database can be represented by a small subset of graph vertices. Searching over only that subset of vertices decreases the response time of a query and increases the efficiency of graph query processing. We introduce the problem of finding a subgraph including the minimum number of vertices as an optimization problem referred to as the minimum hub cover problem. We demonstrate that searching a query over the vertices in minimum hub cover increases the efficiency of query processing and surpasses the existing search methods. We also introduce several mathematical programming models. In particular, we give two binary integer programming formulations as well as a novel quadratic integer programming formulation. We use the linear programming relaxations of the binary integer programming models. Our relaxation for the quadratic integer programming model leads to a semidefinite programming formulation. We also present several rounding heuristics to obtain integral solutions after solving the proposed relaxations. We also focus on planar graphs which have many applications in planar graph query processing and devise fast heuristics with good solution quality for minimum hub cover. We also study an approximation algorithm with a performance guarantee to solve the minimum hub cover problem on planar graphs. We conduct several numerical studies to analyze the empirical performances of solution methods proposed in this thesis.