Search Results

Documents authored by Weberstädt, Grischa

Document
DOI: 10.4230/LIPIcs.STACS.2017.48
Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs

Authors: Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Grischa Weberstädt

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
Bounded expansion and nowhere dense graph classes, introduced by Nesetril and Ossona de Mendez, form a large variety of classes of uniformly sparse graphs which includes the class of planar graphs, actually all classes with excluded minors, and also bounded degree graphs. Since their initial definition it was shown that these graph classes can be defined in many equivalent ways: by generalised colouring numbers, neighbourhood complexity, sparse neighbourhood covers, a game known as the splitter game, and many more. We study the corresponding concepts for directed graphs. We show that the densities of bounded depth directed minors and bounded depth topological minors relate in a similar way as in the undirected case. We provide a characterisation of bounded expansion classes by a directed version of the generalised colouring numbers. As an application we show how to construct sparse directed neighbourhood covers and how to approximate directed distance-r dominating sets on classes of bounded expansion. On the other hand, we show that linear neighbourhood complexity does not characterise directed classes of bounded expansion.
Cite as

Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Grischa Weberstädt. Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kreutzer_et_al:LIPIcs.STACS.2017.48,
  author =	{Kreutzer, Stephan and Rabinovich, Roman and Siebertz, Sebastian and Weberst\"{a}dt, Grischa},
  title =	{{Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{48:1--48:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.48},
  URN =		{urn:nbn:de:0030-drops-69868},
  doi =		{10.4230/LIPIcs.STACS.2017.48},
  annote =	{Keywords: Directed Graph Structure Theory, Bounded Expansion, Generalised Colouring Numbers, Splitter Game, Approximation Algorithms, Dominating Set}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact