Completeness for first-order properties on sparse structures with algorithmic applications. (English) Zbl 1407.68220
Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2162-2181 (2017).
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 03B70 | Logic in computer science |
| 68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68W01 | General topics in the theory of algorithms |
