A PTAS for a disc covering problem using width-bounded separators

DOI10.1007/S10878-006-7132-YMaRDI QIDQ2498985zbMATH OpenOpenAlexFDO

Authors Zhi-Xiang Chen, Bin Fu, Yong Tang, Binhai Zhu

Publication date 14 August 2006

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

Full work available at URL https://doi.org/10.1007/s10878-006-7132-y

zbMATH Keywords

randomized algorithmsapproximation algorithmspolynomial time approximation schemedisc coveringwidth-bounded separator

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Recommendations

• Computing and Combinatorics
• Disc covering problem with application to digital halftoning
• An Almost Linear Time 2.8334-Approximation Algorithm for the Disc Covering Problem
• Theory and application of width bounded geometric separators
• An algorithmic framework for solving geometric covering problems -- with applications

Cites work

• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• Automata, Languages and Programming
• Computational Science and Its Applications – ICCSA 2004
• On the Problem of Partitioning Planar Graphs
• Optimal roundings of sequences and matrices
• Planar Separators

Cited in

(8)

• Theory and Application of Width Bounded Geometric Separator
• Theory and application of width bounded geometric separators
• A lower bound on the area of a 3-coloured disk packing
• A PTAS for the Weighted Unit Disk Cover Problem
• Sublinear time width-bounded separators and their application to the protein side-chain packing problem
• Enabling high-dimensional range queries using \(k\)NN indexing techniques: approaches and empirical results
• Disc covering problem with application to digital halftoning
• Computing and Combinatorics

This page was built for publication: A PTAS for a disc covering problem using width-bounded separators

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