Approximating the minimum hub cover problem on planar graphs

Yelbay, Belma and Birbil, Ş. İlker and Bülbül, Kerem and Jamil, Hasan M. (2016) Approximating the minimum hub cover problem on planar graphs. Optimization Letters, 10 (1). pp. 33-45. ISSN 1862-4472 (Print) 1862-4480 (Online)

This is the latest version of this item.

PDF (This is a RoMEO green journal -- author can archive pre-print (ie pre-refereeing)) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader

Official URL: http://dx.doi.org/10.1007/s11590-015-0876-5


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 isomorphism; 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
ID Code:30478
Deposited By:Kerem Bülbül
Deposited On:12 Nov 2016 15:06
Last Modified:12 Nov 2016 15:06

Available Versions of this Item

Repository Staff Only: item control page