Další formáty:
BibTeX
LaTeX
RIS
@inproceedings{1367542, author = {Gajarský, Jakub and Hliněný, Petr and Lokshtanov, Daniel and Obdržálek, Jan and Ramanujan, M S}, address = {New York, NY, USA}, booktitle = {Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016}, doi = {http://dx.doi.org/10.1145/2933575.2935314}, keywords = {FO Logic; Model-Checking; Logic Interpretations; Sparse Graph Classes; Parameterized Complexity}, howpublished = {tištěná verze "print"}, language = {eng}, location = {New York, NY, USA}, isbn = {978-1-4503-4391-6}, pages = {176-184}, publisher = {ACM}, title = {A New Perspective on FO Model Checking of Dense Graph Classes}, url = {http://lics.rwth-aachen.de/lics16/}, year = {2016} }
TY - JOUR ID - 1367542 AU - Gajarský, Jakub - Hliněný, Petr - Lokshtanov, Daniel - Obdržálek, Jan - Ramanujan, M S PY - 2016 TI - A New Perspective on FO Model Checking of Dense Graph Classes PB - ACM CY - New York, NY, USA SN - 9781450343916 KW - FO Logic KW - Model-Checking KW - Logic Interpretations KW - Sparse Graph Classes KW - Parameterized Complexity UR - http://lics.rwth-aachen.de/lics16/ N2 - We study the FO model checking problem of dense graph classes, namely those which are FO-interpretable in some sparse graph classes. Note that if an input dense graph is given together with the corresponding FO interpretation in a sparse graph, one can easily solve the model checking problem using the existing algorithms for sparse graph classes. However, if the assumed interpretation is not given, then the situation is markedly harder. In this paper we give a structural characterization of graph classes which are FO interpretable in graph classes of bounded degree. This characterization allows us to efficiently compute such an interpretation for an input graph. As a consequence, we obtain an FPT algorithm for FO model checking of graph classes FO interpretable in graph classes of bounded degree. The approach we use to obtain these results may also be of independent interest. ER -
GAJARSKÝ, Jakub, Petr HLINĚNÝ, Daniel LOKSHTANOV, Jan OBDRŽÁLEK a M S RAMANUJAN. A New Perspective on FO Model Checking of Dense Graph Classes. In \textit{Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science LICS2016}. New York, NY, USA: ACM, 2016, s.~176-184. ISBN~978-1-4503-4391-6. Dostupné z: https://dx.doi.org/10.1145/2933575.2935314.
|