First-Order Interpretations of Bounded Expansion Classes
Identifikátory výsledku
Kód výsledku v 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>
Výsledek na webu
<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>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
First-Order Interpretations of Bounded Expansion Classes
Popis výsledku v původním jazyce
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.
Název v anglickém jazyce
First-Order Interpretations of Bounded Expansion Classes
Popis výsledku anglicky
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.
Klasifikace
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)
Návaznosti výsledku
Projekt
<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
Ostatní
Rok uplatnění
2018
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ů
Údaje specifické pro druh výsledku
Název statě ve sborníku
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
ISBN
978-3-95977-076-7
ISSN
1868-8969
e-ISSN
neuvedeno
Počet stran výsledku
14
Strana od-do
1-14
Název nakladatele
Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
Místo vydání
Dagstuhl, Germany
Místo konání akce
Praha
Datum konání akce
9. 7. 2018
Typ akce podle státní příslušnosti
WRD - Celosvětová akce
Kód UT WoS článku
—