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.STACS.2017.48
URN: urn:nbn:de:0030-drops-69868
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6986/
Go to the corresponding LIPIcs Volume Portal

Kreutzer, Stephan ; Rabinovich, Roman ; Siebertz, Sebastian ; Weberstädt, Grischa

Structural Properties and Constant Factor-Approximation of Strong Distance-r Dominating Sets in Sparse Directed Graphs

pdf-format:
LIPIcs-STACS-2017-48.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{kreutzer_et_al:LIPIcs:2017:6986,
  author =	{Stephan Kreutzer and Roman Rabinovich and Sebastian Siebertz and Grischa Weberst{\"a}dt},
  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 =	{Heribert Vollmer and Brigitte Vallée},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6986},
  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}
}

Keywords: Directed Graph Structure Theory, Bounded Expansion, Generalised Colouring Numbers, Splitter Game, Approximation Algorithms, Dominating Set
Collection: 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Issue Date: 2017
Date of publication: 06.03.2017

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