On streaming algorithms for geometric independent set and clique

DOI10.1007/978-3-031-18367-6_11arXiv2207.01108OpenAlexW4312740989MaRDI QIDQ6176560

Jelle J. Oostveen, Fabian Klute, Sujoy Bhore

Publication date: 25 July 2023

Published in: Approximation and Online Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

streaming algorithmsgeometric intersection graphscommunication lower boundsgeometric independent set

Mathematics Subject Classification ID

Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximation algorithms for maximum independent set of pseudo-disks
• Dynamic algorithms for monotonic interval scheduling problem
• Interval scheduling and colorful independent sets
• Label placement by maximum independent set in rectangles
• The space complexity of approximating the frequency moments
• Interval selection in the streaming model
• Independent set of intersection graphs of convex objects in 2D
• Coresets in dynamic geometric data streams
• Streaming Algorithms for Independent Sets
• Finding a Maximum Clique in an Arbitrary Graph
• Space-Constrained Interval Selection
• Reducibility among Combinatorial Problems
• Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Scheduling Split Intervals
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• A unified approach to approximating resource allocation and scheduling
• Algorithms - ESA 2003
• Weighted Maximum Independent Set of Geometric Objects in Turnstile Streams.
• Worst-Case Efficient Dynamic Geometric Independent Set

This page was built for publication: On streaming algorithms for geometric independent set and clique