Algorithmic Properties of Sparse Digraphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F19%3A10422242" target="_blank" >RIV/00216208:11320/19:10422242 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Algorithmic Properties of Sparse Digraphs

Popis výsledku v původním jazyce

The notions of bounded expansion [56] and nowhere denseness [58], introduced by Negetfil and Ossona de Mendez as structural measures for undirected graphs, have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs, introduced by Kreutzer and Tazari [48]. The classes of directed graphs having those properties are very general classes of sparse directed graphs, as they include, on one hand, all classes of directed graphs whose underlying undirected class has bounded expansion, such as planar, bounded -genus, and H -minor -free graphs, and on the other hand, they also contain classes whose underlying undirected class is not even nowhere dense. We show that many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion and nowhere crownful classes.

Název v anglickém jazyce

Algorithmic Properties of Sparse Digraphs

Popis výsledku anglicky

The notions of bounded expansion [56] and nowhere denseness [58], introduced by Negetfil and Ossona de Mendez as structural measures for undirected graphs, have been applied very successfully in algorithmic graph theory. We study the corresponding notions of directed bounded expansion and nowhere crownfulness on directed graphs, introduced by Kreutzer and Tazari [48]. The classes of directed graphs having those properties are very general classes of sparse directed graphs, as they include, on one hand, all classes of directed graphs whose underlying undirected class has bounded expansion, such as planar, bounded -genus, and H -minor -free graphs, and on the other hand, they also contain classes whose underlying undirected class is not even nowhere dense. We show that many of the algorithmic tools that were developed for undirected bounded expansion classes can, with some care, also be applied in their directed counterparts, and thereby we highlight a rich algorithmic structure theory of directed bounded expansion and nowhere crownful classes.

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/LL1201" target="_blank" >LL1201: Komplexní Struktury: Regularita v Kombinatorice a Diskrétní Matematice</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í

2019

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

36TH INTERNATIONAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE (STACS 2019)

ISBN

978-3-95977-100-9

ISSN

—

e-ISSN

—

Počet stran výsledku

20

Strana od-do

—

Název nakladatele

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS

Místo vydání

WADEM

Místo konání akce

Berlin

Datum konání akce

13. 3. 2019

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

WRD - Celosvětová akce

Kód UT WoS článku

000472795800045