Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

DOI10.4230/LIPICS.SOCG.2020.51MaRDI QIDQ6060002zbMATH OpenFDO

Authors Monika R. Henzinger, Stefan Neumann, Andreas Wiese

Publication date 2 November 2023

Full work available at URL https://arxiv.org/abs/2003.02605

zbMATH Keywords

approximation algorithmsdynamic algorithmsgeometric intersection graphsindependent setinterval graphs

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Dynamic geometric set cover, revisited
• Maximum independent set of rectangles
• A note on maximum independent sets in rectangle intersection graphs
• Dynamic Geometric Set Cover and Hitting Set

Cited in

(12)

• Robust online algorithms for dynamic choosing problems
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• Temporal interval cliques and independent sets
• On streaming algorithms for geometric independent set and clique
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic geometric set cover, revisited
• More dynamic data structures for geometric set cover with sublinear update time
• Random-order online independent set of intervals and hyperrectangles
• Fully dynamic maximum independent sets of disks in polylogarithmic update time
• Dynamic streaming algorithms for geometric independent set
• Dynamic maximum depth of geometric objects

This page was built for publication: Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

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