The Library
The sparse awakens : streaming algorithms for matching size estimation in sparse graphs
Tools
Cormode, Graham, Jowhari, Hossein, Monemizadeh, Morteza and Muthukrishnan, S. (2017) The sparse awakens : streaming algorithms for matching size estimation in sparse graphs. In: ESA 2017 – The 25th Annual European Symposium on Algorithms, Vienna, Austria, 04-08 Sep 2017. Published in: ALGO 2017, 2017
PDF
WRAP-Sparse-awakens-streaming-algorithms-Cormode-2017.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (880Kb) |
Official URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.29
Abstract
Estimating the size of the maximum matching is a canonical problem in graph analysis, and one that has attracted extensive study over a range of different computational models. We present improved streaming algorithms for approximating the size of maximum matching with sparse (bounded arboricity) graphs.
(Insert-Only Streams) We present a one-pass algorithm that takes O(α log n) space and approximates the size of the maximum matching in graphs with arboricity α within a factor of O(α). This improves significantly upon the state-of-the-art O˜(αn2/3)-space streaming algorithms, and is the first poly-logarithmic space algorithm for this problem.
(Dynamic Streams) Given a dynamic graph stream (i.e., inserts and deletes) of edges of an underlying α-bounded arboricity graph, we present an one-pass algorithm that uses space
O˜(α10/3n2/3) and returns an O(α)-estimator for the size of the maximum matching on the condition that the number edge deletions in the stream is bounded by O(αn). For this class of inputs, our algorithm improves the state-of-the-art O˜(αn4/5)-space algorithms, where the O˜(.) notation hides logarithmic in n dependencies.
In contrast to prior work, our results take more advantage of the streaming access to the input and characterize the matching size based on the ordering of the edges in the stream in addition to the degree distributions and structural properties of the sparse graphs.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Graph theory, Graph algorithms, Computer algorithms, Data mining | ||||||
Journal or Publication Title: | ALGO 2017 | ||||||
Publisher: | Algorithms and Complexity Group | ||||||
Official Date: | September 2017 | ||||||
Dates: |
|
||||||
Volume: | 2017 | ||||||
Status: | Not Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 18 September 2017 | ||||||
Funder: | European Research Council (ERC), Engineering and Physical Sciences Research Council (EPSRC), Royal Society (Great Britain). Wolfson Research Merit Award (RSWRMA) | ||||||
Grant number: | ERC-2014-CoG 647557 (ERC), EP/N510129/1 (EPSRC), | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | ESA 2017 – The 25th Annual European Symposium on Algorithms | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Vienna, Austria | ||||||
Date(s) of Event: | 04-08 Sep 2017 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |