Minimum hub cover problem: solution methods and applications

Yelbay, Belma (2014) Minimum hub cover problem: solution methods and applications. [Thesis]

[thumbnail of BelmaYelbay_10049245.pdf] PDF
BelmaYelbay_10049245.pdf

Download (1MB)

Abstract

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.
Item Type: Thesis
Uncontrolled Keywords: Minimum hub cover problem. -- Graph query processing. -- Graph covering problem. -- En küçük göbek kapsama problemi. -- Çizge sorgu işleme. -- Çizge kapsama problemi.
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Industrial Engineering
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 07 Apr 2016 14:14
Last Modified: 26 Apr 2022 10:06
URI: https://research.sabanciuniv.edu/id/eprint/29273

Actions (login required)

View Item
View Item