License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.2
URN: urn:nbn:de:0030-drops-99505
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9950/
Go to the corresponding LIPIcs Volume Portal

Stein, Clifford

Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)

pdf-format:
LIPIcs-ISAAC-2018-2.pdf (0.2 MB)

Abstract

Finding a maximum matching is a fundamental algorithmic problem and is fairly well understood in traditional sequential computing models. Some modern applications require that we handle massive graphs and hence we need to consider algorithms in models that do not allow the entire input graph to be held in the memory of one computer, or models in which the graph is evolving over time.
We introduce a new concept called an "Edge Degree Constrained Subgraph (EDCS)", which is a subgraph that is guaranteed to contain a large matching, and which can be identified via local conditions. We then show how to use an EDCS to find 1.5-approximate matchings in several different models including Map Reduce, streaming and distributed computing. We can also use an EDCS to maintain a 1.5-optimal matching in a dynamic graph.
This work is joint with Sepehr Asadi, Aaron Bernstein, Mohammad Hossein Bateni and Vahab Marrokni.

BibTeX - Entry

@InProceedings{stein:LIPIcs:2018:9950,
  author =	{Clifford Stein},
  title =	{{Approximate Matchings in Massive Graphs via Local Structure (Invited Talk)}},
  booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-094-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{123},
  editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9950},
  URN =		{urn:nbn:de:0030-drops-99505},
  doi =		{10.4230/LIPIcs.ISAAC.2018.2},
  annote =	{Keywords: matching, dynamic algorithms, parallel algorithms, approximation algorithms}
}

Keywords: matching, dynamic algorithms, parallel algorithms, approximation algorithms
Collection: 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Issue Date: 2018
Date of publication: 06.12.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI