Testing First-Order Properties for Subclasses of Sparse Graphs

J 2013

Testing First-Order Properties for Subclasses of Sparse Graphs

DVORAK, Z; Daniel KRÁĽ a R THOMAS

Základní údaje

Originální název

Testing First-Order Properties for Subclasses of Sparse Graphs

Autoři

DVORAK, Z; Daniel KRÁĽ a R THOMAS

Vydání

Journal of the ACM, NEW YORK, ASSOC COMPUTING MACHINERY, 2013, 0004-5411

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 2.939

DOI

https://doi.org/10.1145/2499483

UT WoS

000326321500007

Klíčová slova anglicky

Algorithms; Theory; First-order model checking; graphs with bounded expansion; tree-depth

Změněno: 4. 11. 2020 13:50, Mgr. Darina Boukalová

Anotace

V originále

We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.

Citovat

DVORAK, Z; Daniel KRÁĽ a R THOMAS. Testing First-Order Properties for Subclasses of Sparse Graphs. Journal of the ACM. NEW YORK: ASSOC COMPUTING MACHINERY, 2013, roč. 60, č. 5, 24 s. ISSN 0004-5411. Dostupné z: https://doi.org/10.1145/2499483.

@article{1688920,
   author = {Dvorak, Z and Kráľ, Daniel and Thomas, R},
   article_location = {NEW YORK},
   article_number = {5},
   doi = {https://doi.org/10.1145/2499483},
   keywords = {Algorithms; Theory; First-order model checking; graphs with bounded expansion; tree-depth},
   language = {eng},
   issn = {0004-5411},
   journal = {Journal of the ACM},
   title = {Testing First-Order Properties for Subclasses of Sparse Graphs},
   volume = {60},
   year = {2013}
}

TY  - JOUR
ID  - 1688920
AU  - Dvorak, Z - Kráľ, Daniel - Thomas, R
PY  - 2013
TI  - Testing First-Order Properties for Subclasses of Sparse Graphs
JF  - Journal of the ACM
VL  - 60
IS  - 5
PB  - ASSOC COMPUTING MACHINERY
SN  - 00045411
KW  - Algorithms
KW  - Theory
KW  - First-order model checking
KW  - graphs with bounded expansion
KW  - tree-depth
N2  - We present a linear-time algorithm for deciding first-order (FO) properties in classes of graphs with bounded expansion, a notion recently introduced by Nesetril and Ossona de Mendez. This generalizes several results from the literature, because many natural classes of graphs have bounded expansion: graphs of bounded tree-width, all proper minor-closed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We deduce that there is an almost linear-time algorithm for deciding FO properties in classes of graphs with locally bounded expansion. More generally, we design a dynamic data structure for graphs belonging to a fixed class of graphs of bounded expansion. After a linear-time initialization the data structure allows us to test an FO property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their simultaneous addition results in a graph in the class. All our results also hold for relational structures and are based on the seminal result of Nesetril and Ossona de Mendez on the existence of low tree-depth colorings.
ER  -

DVORAK, Z; Daniel KRÁĽ a R THOMAS. Testing First-Order Properties for Subclasses of Sparse Graphs. \textit{Journal of the ACM}. NEW YORK: ASSOC COMPUTING MACHINERY, 2013, roč.~60, č.~5, 24 s. ISSN~0004-5411. Dostupné z: https://doi.org/10.1145/2499483.

Přehled o publikaci