Dynamic approximate maximum independent set of intervals, hypercubes and hyperrectangles

DOI10.4230/LIPICS.SOCG.2020.51arXiv2003.02605MaRDI QIDQ6060002FDOQ6060002

Authors: Monika R. Henzinger, Stefan Neumann, Andreas Wiese 

Publication date: 2 November 2023

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

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

zbMATH Keywords

approximation algorithmsinterval graphsindependent setgeometric intersection graphsdynamic algorithms

Mathematics Subject Classification ID

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

Cited In (5)

• Robust online algorithms for dynamic choosing problems
• Temporal interval cliques and independent sets
• New partitioning techniques and faster algorithms for approximate interval scheduling
• Title not available (Why is that?)
• On streaming algorithms for geometric independent set and clique

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)