Optimization Online


Approximating the Minimum Hub Cover Problem on Planar Graphs

Belma Yelbay (byelbay***at***sabanciuniv.edu)
S. Ilker Birbil (sibirbil***at***sabanciuniv.edu)
Kerem Bulbul (bulbul***at***sabanciuniv.edu)
Hasan M. Jamil (jamil***at***uidaho.edu)

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.

Keywords: approximation algorithm, query processing, subgraph isomorphism, planar graph decomposition, minimum hub cover problem

Category 1: Applications -- Science and Engineering

Category 2: Combinatorial Optimization (Approximation Algorithms )

Citation: Yelbay, B., Birbil, S.I., Bulbul, K., and Jamil, H.M. (2016). Approximating the Minimum Hub Cover Problem on Planar Graphs. Optimization Letters, 10(1):33-45. http://dx.doi.org/10.1007/s11590-015-0876-5

Download: [PDF]

Entry Submitted: 11/30/2014
Entry Accepted: 11/30/2014
Entry Last Modified: 10/29/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society