Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs
From MaRDI portal
Publication:6179417
DOI10.1007/978-3-031-38906-1_17arXiv2305.16815MaRDI QIDQ6179417
Anthony Wirth, Patrick Eades, Rajesh Chitnis, Xiuge Chen
Publication date: 16 January 2024
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2305.16815
Cites Work
- Unnamed Item
- Streaming algorithms for independent sets in sparse hypergraphs
- On total domination and support vertices of a tree
- Greed is good: Approximating independent sets in sparse and bounded-degree graphs
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Approximating the Caro-Wei bound for independent sets in graph streams
- Structural results on matching estimation with applications to streaming
- A lower bound for the distance \(k\)-domination number of trees
- On graph problems in a semi-streaming model
- A Small Approximately Min-Wise Independent Family of Hash Functions
- Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
- Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
- Lower bound on the domination number of a tree
- An improved data stream summary: the count-min sketch and its applications
- Reducibility among Combinatorial Problems
- The sparse awakens: Streaming algorithms for matching size estimation in sparse graphs
- Evaluation of Labeling Strategies for Rotating Maps
- Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond
- Simple and local independent set approximation
This page was built for publication: Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs