Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs

DOI10.1142/S0218195917500078zbMath1386.68226OpenAlexW2964282814MaRDI QIDQ4605337

Celina Miraglia Herrera de Figueiredo, Vinícius Gusmão Pereira de Sá, Guilherme Dias da Fonseca

Publication date: 22 February 2018

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195917500078

zbMATH Keywords

approximation algorithmunit disk graphgeometric intersection graphcoreset

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (1)

On reverse shortest paths in geometric proximity graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of a unit disk graph
• A note on maximum independent sets in rectangle intersection graphs
• The complexity of finding fixed-radius near neighbors
• Label placement by maximum independent set in rectangles
• Efficient independent set approximation in unit disk graphs
• Efficient sub-5 approximations for minimum dominating sets in unit disk graphs
• Independent set of intersection graphs of convex objects in 2D
• A linear-time approximation algorithm for weighted matchings in graphs
• Linear-Time Approximation for Maximum Weight Matching
• Minimum Dominating Set Problem for Unit Disks Revisited
• Approximation schemes for covering and packing problems in image processing and VLSI
• Approximation algorithms for NP-complete problems on planar graphs
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks
• Near-Linear Algorithms for Geometric Hitting Sets and Set Covers
• Simple heuristics for unit disk graphs
• A new proof of the 6 color theorem
• Approximation schemes for wireless networks
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• Algorithms – ESA 2005

This page was built for publication: Shifting Coresets: Obtaining Linear-Time Approximations for Unit Disk Graphs and Other Geometric Intersection Graphs