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

Dvořák, Zdeněk

Representation of Short Distances in Structurally Sparse Graphs

pdf-format:
LIPIcs-STACS-2023-28.pdf (0.7 MB)

Abstract

A partial orientation H of a graph G is a weak r-guidance system if for any two vertices at distance at most r in G, there exists a shortest path P between them such that H directs all but one edge in P towards this edge. In case that H has bounded maximum outdegree Δ, this gives an efficient representation of shortest paths of length at most r in G: For any pair of vertices, we can either determine the distance between them or decide the distance is more than r, and in the former case, find a shortest path between them, in time O(Δ^r). We show that graphs from many natural graph classes admit such weak guidance systems, and study the algorithmic aspects of this notion. We also apply the notion to obtain approximation algorithms for distance variants of the independence and domination number in graph classes that admit weak guidance systems of bounded maximum outdegree.

BibTeX - Entry

@InProceedings{dvorak:LIPIcs.STACS.2023.28,
  author =	{Dvo\v{r}\'{a}k, Zden\v{e}k},
  title =	{{Representation of Short Distances in Structurally Sparse Graphs}},
  booktitle =	{40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
  pages =	{28:1--28:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-266-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{254},
  editor =	{Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17680},
  URN =		{urn:nbn:de:0030-drops-176807},
  doi =		{10.4230/LIPIcs.STACS.2023.28},
  annote =	{Keywords: distances, structurally sparse graphs}
}

Keywords: distances, structurally sparse graphs
Collection: 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Issue Date: 2023
Date of publication: 03.03.2023

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