Minimum vertex cover in ball graphs through local search
From MaRDI portal
Publication:2250102
DOI10.1007/S10898-013-0116-4zbMATH Open1301.90093OpenAlexW2134480399MaRDI QIDQ2250102FDOQ2250102
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
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
- Introduction to algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Optimization, approximation, and complexity classes
- Approximation algorithms for NP-complete problems on planar graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the hardness of approximating minimum vertex cover
- A Separator Theorem for Planar Graphs
- Title not available (Why is that?)
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Separators for sphere-packings and nearest neighbor graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Simple heuristics for unit disk graphs
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Approximation algorithms for maximum independent set of pseudo-disks
- PTAS for geometric hitting set problems via local search
- Algorithms for dominating set in disk graphs: breaking the \(\log n\) barrier (extended abstract)
- Domination in Geometric Intersection Graphs
- Automata, Languages and Programming
- Separators in graphs with negative and multiple vertex weights
Cited In (6)
- Title not available (Why is that?)
- 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)
