DROPS

Document

DOI: 10.4230/OASIcs.SOSA.2018.14

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs

Authors: Andrew McGregor and Sofya Vorotnikova

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract

We present a simple single-pass data stream algorithm using O((log n)/eps^2) space that returns an (alpha + 2)(1 + eps) approximation to the size of the maximum matching in a graph of arboricity alpha.

Cite as

Andrew McGregor and Sofya Vorotnikova. A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 14:1-14:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{mcgregor_et_al:OASIcs.SOSA.2018.14,
  author =	{McGregor, Andrew and Vorotnikova, Sofya},
  title =	{{A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{14:1--14:4},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.14},
  URN =		{urn:nbn:de:0030-drops-82959},
  doi =		{10.4230/OASIcs.SOSA.2018.14},
  annote =	{Keywords: data streams, matching, planar graphs, arboricity}
}

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2016.17

Planar Matching in Streams Revisited

Authors: Andrew McGregor and Sofya Vorotnikova

Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)

Abstract

We present data stream algorithms for estimating the size or weight of the maximum matching in low arboricity graphs. A large body of work has focused on improving the constant approximation factor for general graphs when the data stream algorithm is permitted O(n polylog n) space where n is the number of nodes. This space is necessary if the algorithm must return the matching. Recently, Esfandiari et al. (SODA 2015) showed that it was possible to estimate the maximum cardinality of a matching in a planar graph up to a factor of 24+epsilon using O(epsilon^{-2} n^{2/3} polylog n) space. We first present an algorithm (with a simple analysis) that improves this to a factor 5+epsilon using the same space. We also improve upon the previous results for other graphs with bounded arboricity. We then present a factor 12.5 approximation for matching in planar graphs that can be implemented using O(log n) space in the adjacency list data stream model where the stream is a concatenation of the adjacency lists of the graph. The main idea behind our results is finding "local" fractional matchings, i.e., fractional matchings where the value of any edge e is solely determined by the edges sharing an endpoint with e. Our work also improves upon the results for the dynamic data stream model where the stream consists of a sequence of edges being inserted and deleted from the graph. We also extend our results to weighted graphs, improving over the bounds given by Bury and Schwiegelshohn (ESA 2015), via a reduction to the unweighted problem that increases the approximation by at most a factor of two.

Cite as

Andrew McGregor and Sofya Vorotnikova. Planar Matching in Streams Revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 17:1-17:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{mcgregor_et_al:LIPIcs.APPROX-RANDOM.2016.17,
  author =	{McGregor, Andrew and Vorotnikova, Sofya},
  title =	{{Planar Matching in Streams Revisited}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)},
  pages =	{17:1--17:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-018-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{60},
  editor =	{Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.17},
  URN =		{urn:nbn:de:0030-drops-66407},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2016.17},
  annote =	{Keywords: data streams, planar graphs, arboricity, matchings}
}

Search Results

Documents authored by Vorotnikova, Sofya

A Simple, Space-Efficient, Streaming Algorithm for Matchings in Low Arboricity Graphs

Abstract

Cite as

Planar Matching in Streams Revisited

Abstract

Cite as

Thanks for your feedback!

Could not send message