License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.4
URN: urn:nbn:de:0030-drops-144445
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14444/
Go to the corresponding LIPIcs Volume Portal

Rotenberg, Eva

On Dynamic Graphs (Invited Talk)

pdf-format:
LIPIcs-MFCS-2021-4.pdf (0.3 MB)

Abstract

In graph algorithms, many questions about a graph can be answered in time proportional to the size of the input, and such linear time algorithms are considered the epitome of efficiency. However, when the graph changes slightly, e.g. by the insertion or deletion of an edge or a vertex, it is undesirable to consider the entire input again. Rather, one would wish to keep some of the partial answers to questions about the old graph, and re-use them when computing answers to questions about the resulting graph. The art of handling such changes is studied in dynamic graph algorithms.
In this talk, we will see some examples of ideas and techniques for efficiently maintaining knowledge about a dynamically changing graph. We will consider classical and natural graph properties such as connectivity and planarity, and we will focus on deterministic algorithms.

BibTeX - Entry

@InProceedings{rotenberg:LIPIcs.MFCS.2021.4,
  author =	{Rotenberg, Eva},
  title =	{{On Dynamic Graphs}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{4:1--4:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14444},
  URN =		{urn:nbn:de:0030-drops-144445},
  doi =		{10.4230/LIPIcs.MFCS.2021.4},
  annote =	{Keywords: Graph algorithms, dynamic graphs, connectivity, planarity, matching, online algorithms}
}

Keywords: Graph algorithms, dynamic graphs, connectivity, planarity, matching, online algorithms
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

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