Sublinear-space streaming algorithms for estimating graph parameters on sparse graphs

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

zbMATH Keywords

matchingindependent setgraph algorithmsdominating setCaro-Wei bounddata streams model

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

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