Belma Yelbay 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 … Read more
The use of graph databases for social networks, images, web links, pathways and so on, has been increasing at a fast pace and promotes the need for efficient graph query processing on such databases. In this study, we discuss graph query processing — referred to as graph matching — and an inherent optimization problem known … Read more
This paper investigates the role of dual information on the performances of heuristics designed for solving the set covering problem. After solving the linear programming relaxation of the problem, the dual information is used to obtain the two main approaches proposed here: (i) The size of the original problem is reduced and then the resulting … Read more