Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
From MaRDI portal
Publication:6058197
DOI10.4230/lipics.approx/random.2020.64arXiv1902.10328OpenAlexW3082617830MaRDI QIDQ6058197
Ainesh Bakshi, David P. Woodruff, Unnamed Author
Publication date: 31 October 2023
Full work available at URL: https://arxiv.org/abs/1902.10328
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Approximation algorithms for maximum independent set of pseudo-disks
- Probabilistic counting algorithms for data base applications
- Optimal packing and covering in the plane are NP-complete
- Unit disk graphs
- On data structures and asymmetric communication complexity
- Label placement by maximum independent set in rectangles
- On-line scheduling of jobs with fixed start and end times
- Interval selection in the streaming model
- Space-Constrained Interval Selection
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Optimal Streaming and Tracking Distinct Elements with High Probability
- Buffer Management for Packets with Processing Times
- Maximum Matching in Turnstile Streams
- Interval scheduling: A survey
- Approximation schemes for covering and packing problems in image processing and VLSI
- Bounding the Power of Preemption in Randomized Scheduling
- Polynomial-time approximation schemes for packing and piercing fat objects
- Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
- Contact graphs of line segments are NP-complete
This page was built for publication: Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
