Minimum vertex cover in ball graphs through local search

DOI10.1007/S10898-013-0116-4MaRDI QIDQ2250102zbMATH OpenOpenAlexFDO

Authors Zhao Zhang, Weili Wu, Lidan Fan, Du Ding-Zhu

Publication date 4 July 2014

Published in Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10898-013-0116-4

zbMATH Keywords

local searchvertex coverball graphseparator theorem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• An approximation of the minimum vertex cover in a graph
• A Local 2-Approximation Algorithm for the Vertex Cover Problem
• PTAS for minimum \(k\)-path vertex cover in ball graph
• A simple local 3-approximation algorithm for vertex cover
• Polynomial Time Approximation Scheme for Connected Vertex Cover in Unit Disk Graph

Cites work

• scientific article; zbMATH DE number 3889282 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation algorithms for maximum independent set of pseudo-disks
• Approximation schemes for covering and packing problems in image processing and VLSI
• Automata, Languages and Programming
• Domination in Geometric Intersection Graphs
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Introduction to algorithms
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• On the hardness of approximating minimum vertex cover
• Optimization, approximation, and complexity classes
• PTAS for geometric hitting set problems via local search
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• Ramsey numbers and an approximation algorithm for the vertex cover problem
• Separators for sphere-packings and nearest neighbor graphs
• Separators in graphs with negative and multiple vertex weights
• Simple heuristics for unit disk graphs

Cited in

(6)

• scientific article; zbMATH DE number 6303718 (Why is no real title available?)
• Multi-start iterated tabu search for the minimum weight vertex cover problem
• On approximability of minimum color-spanning ball in high dimensions
• PTAS for minimum \(k\)-path vertex cover in ball graph
• PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs
• Solving the multistage PMU placement problem by integer programming and equivalent network design model

This page was built for publication: Minimum vertex cover in ball graphs through local search

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