Minimum vertex cover in ball graphs through local search
From MaRDI portal
Publication:2250102
DOI10.1007/s10898-013-0116-4zbMath1301.90093OpenAlexW2134480399MaRDI QIDQ2250102
Lidan Fan, Ding-Zhu Du, Weili Wu, Zhao Zhang
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
Related Items
Multi-start iterated tabu search for the minimum weight vertex cover problem, Solving the multistage PMU placement problem by integer programming and equivalent network design model, PTAS for \(\mathcal{H}\)-free node deletion problems in disk graphs, PTAS for minimum \(k\)-path vertex cover in ball graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- On the hardness of approximating minimum vertex cover
- Optimization, approximation, and complexity classes
- Separators in graphs with negative and multiple vertex weights
- Algorithms for Dominating Set in Disk Graphs: Breaking the logn Barrier
- Approximation schemes for covering and packing problems in image processing and VLSI
- Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
- A Separator Theorem for Planar Graphs
- Approximation algorithms for NP-complete problems on planar graphs
- 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
- PTAS for geometric hitting set problems via local search
- Domination in Geometric Intersection Graphs
- Automata, Languages and Programming