Approximating the minimum hub cover problem on planar graphs

Yelbay, Belma and Birbil, Ş. İlker and Bülbül, Kerem and Jamil, Hasan M. (2015) Approximating the minimum hub cover problem on planar graphs. Optimization Letters . ISSN 1862-4472 (Print) 1862-4480 (Online) Published Online First http://dx.doi.org/10.1007/s11590-015-0876-5

Warning
There is a more recent version of this item available.
[thumbnail of This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)] PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing))
MHC_Planar_Application.pdf

Download (494kB)

Abstract

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 applications, such as; biometric identification, image classification, object recognition, and so on. Our algorithm is based on a well-known graph decomposition technique that partitions the graph into a set of outerplanar graphs and provides an approximate solution with a proven performance ratio. We conduct a comprehensive computational experiment to investigate the empirical performance of the algorithm. Computational results demonstrate that the empirical performance of the algorithm surpasses its guaranteed performance. We also apply the same decomposition approach to develop a decomposition-based heuristic, which is much more efficient than the approximation algorithm in terms of computation time. Computational results also indicate that the efficacy of the decomposition-based heuristic in terms of solution quality is comparable to that of the approximation algorithm.
Item Type: Article
Uncontrolled Keywords: approximation algorithm, query processing, subgraph isom orphism, planar graph decomposition, minimum hub cover problem
Subjects: T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering
T Technology > T Technology (General) > T055.4-60.8 Industrial engineering. Management engineering > T57.6-57.97 Operations research. Systems analysis
Divisions: Faculty of Engineering and Natural Sciences
Faculty of Engineering and Natural Sciences > Academic programs > Manufacturing Systems Eng.
Depositing User: Kerem Bülbül
Date Deposited: 05 Oct 2015 15:11
Last Modified: 26 Apr 2022 09:23
URI: https://research.sabanciuniv.edu/id/eprint/27188

Available Versions of this Item

Actions (login required)

View Item
View Item