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 algorithmsinterval graphsindependent setgeometric intersection graphsdynamic algorithms

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

(5)

• Temporal interval cliques and independent sets
• Robust online algorithms for dynamic choosing problems
• New partitioning techniques and faster algorithms for approximate interval scheduling
• On streaming algorithms for geometric independent set and clique
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)

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)