  


Approximating the Minimum Hub Cover Problem on Planar Graphs
Belma Yelbay (byelbaysabanciuniv.edu) Abstract: We study an approximation algorithm with a performance guarantee to solve a new NPhard 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 wellknown 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 decompositionbased heuristic, which is much more efficient than the approximation algorithm in terms of computation time. Computational results also indicate that the efficacy of the decompositionbased 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):3345. http://dx.doi.org/10.1007/s1159001508765 Download: [PDF] Entry Submitted: 11/30/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  