First-Order Interpretations of Bounded Expansion Classes

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10387240" target="_blank" >RIV/00216208:11320/18:10387240 - isvavai.cz</a>

Result on the web

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

DOI - Digital Object Identifier

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

Result language

angličtina

Original language name

First-Order Interpretations of Bounded Expansion Classes

Original language description

The notion of bounded expansion captures uniform sparsity of graph classes and renders various algorithmic problems that are hard in general tractable. In particular, the model-checking problem for first-order logic is fixed-parameter tractable over such graph classes. With the aim of generalizing such results to dense graphs, we introduce classes of graphs with structurally bounded expansion, defined as first-order interpretations of classes of bounded expansion. As a first step towards their algorithmic treatment, we provide their characterization analogous to the characterization of classes of bounded expansion via low treedepth decompositions, replacing treedepth by its dense analogue called shrubdepth.

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/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2018

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

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

ISBN

978-3-95977-076-7

ISSN

1868-8969

e-ISSN

neuvedeno

Number of pages

14

Pages from-to

1-14

Publisher name

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik

Place of publication

Dagstuhl, Germany

Event location

Praha

Event date

Jul 9, 2018

Type of event by nationality

WRD - Celosvětová akce

UT code for WoS article

—