Representation of Short Distances in Structurally Sparse Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Representation of Short Distances in Structurally Sparse Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Representation of Short Distances in Structurally Sparse Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

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

Projekt

<a href="/cs/project/LL2005" target="_blank" >LL2005: Algoritmy a složitost v rámci a nad omezenou expanzí</a><br>

Návaznosti

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

Rok uplatnění

2023

Kód důvěrnosti údajů

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

Název statě ve sborníku

Leibniz International Proceedings in Informatics, LIPIcs

ISBN

978-3-95977-266-2

ISSN

—

e-ISSN

—

Počet stran výsledku

22

Strana od-do

1-22

Název nakladatele

Schloss-Dagstuhl - Leibniz Zentrum für Informatik

Místo vydání

Wadern, Germany

Místo konání akce

Hamburg, Germany

Datum konání akce

7. 3. 2023

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—