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

DOI10.1007/s10878-006-7132-yzbMath1130.90050OpenAlexW2060662766MaRDI QIDQ2498985

Binhai Zhu, Yong Tang, Bin Fu, Zhixiang Chen

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

approximation algorithmsrandomized 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)

Related Items (3)

Enabling high-dimensional range queries using \(k\)NN indexing techniques: approaches and empirical results ⋮ Sublinear time width-bounded separators and their application to the protein side-chain packing problem ⋮ A LOWER BOUND ON THE AREA OF A 3-COLOURED DISK PACKING

Cites Work

• A Separator Theorem for Planar Graphs
• On the Problem of Partitioning Planar Graphs
• Planar Separators
• Automata, Languages and Programming
• Computational Science and Its Applications – ICCSA 2004
• Unnamed Item
• Unnamed Item

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