Approximating the minimum hub cover problem on planar graphs

DOI10.1007/S11590-015-0876-5MaRDI QIDQ5963689zbMATH OpenOpenAlexFDO

Authors Belma Yelbay, Ş. İlker Birbil, Kerem Bülbül, Hasan M. Jamil

Publication date 23 February 2016

Published in Optimization Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11590-015-0876-5

zbMATH Keywords

approximation algorithmsubgraph isomorphismquery processingplanar graph decompositionminimum hub cover problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Recommendations

• scientific article; zbMATH DE number 3966112
• scientific article; zbMATH DE number 7399666
• A graph approximation heuristic for the vertex cover problem on planar graphs
• An approximation of the minimum vertex cover in a graph
• Approximation algorithm for the minimum connected \(k\)-path vertex cover problem
• Approximation algorithms for NP-complete problems on planar graphs
• On the complexity of planar covering of small graphs
• scientific article; zbMATH DE number 2009908
• On the hardness of approximating minimum vertex cover
• scientific article; zbMATH DE number 5631194

Cites work

• An Algorithm for Subgraph Isomorphism
• Approximation algorithms for NP-complete problems on planar graphs
• Determining the Smallest k Such That G Is k-Outerplanar
• Efficient Planarity Testing
• Object Recognition Through Topo-Geometric Shape Models Using Error-Tolerant Subgraph Isomorphisms
• On the complexity of embedding planar graphs to minimize certain distance measures
• Some simplified NP-complete graph problems
• The complexity of theorem-proving procedures

Cited in

(1)

• A fast approximation algorithm for the maximum 2-packing set problem on planar graphs

This page was built for publication: Approximating the minimum hub cover problem on planar graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5963689)