Representation of Short Distances in Structurally Sparse Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F23%3A10473811" target="_blank" >RIV/00216208:11320/23:10473811 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.4230/LIPIcs.STACS.2023.28" target="_blank" >https://doi.org/10.4230/LIPIcs.STACS.2023.28</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.4230/LIPIcs.STACS.2023.28" target="_blank" >10.4230/LIPIcs.STACS.2023.28</a>

Result language

angličtina

Original language name

Representation of Short Distances in Structurally Sparse Graphs

Original language description

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 Delta , 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(Delta^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.

Czech name

—

Czech description

—

Type

D - Article in proceedings

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/LL2005" target="_blank" >LL2005: Algorithms and Complexity within and beyond Bounded Expansion</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2023

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Article name in the collection

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-266-2

ISSN

—

e-ISSN

—

Number of pages

22

Pages from-to

1-22

Publisher name

Schloss-Dagstuhl - Leibniz Zentrum für Informatik

Place of publication

Wadern, Germany

Event location

Hamburg, Germany

Event date

Mar 7, 2023

Type of event by nationality

CST - Celostátní akce

UT code for WoS article

—