Algorithmic Properties of Sparse Digraphs

Result code in 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>

Result on the web

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

Result language

angličtina

Original language name

Algorithmic Properties of Sparse Digraphs

Original language description

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.

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/LL1201" target="_blank" >LL1201: Complex Structures: Regularities in Combinatorics and Discrete Mathematics</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

2019

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

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

ISBN

978-3-95977-100-9

ISSN

—

e-ISSN

—

Number of pages

20

Pages from-to

—

Publisher name

SCHLOSS DAGSTUHL, LEIBNIZ CENTER INFORMATICS

Place of publication

WADEM

Event location

Berlin

Event date

Mar 13, 2019

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

000472795800045