The betweenness centrality of a vertex v is an important centrality measure that quantifies
how many optimal paths between pairs of other vertices visit v. Computing betweenness …

Disjoint-paths logic, denoted FO+ DP, extends first-order logic (FO) with atomic predicates
dp k [(x 1, y 1),…,(xk, yk)], expressing the existence of internally vertex-disjoint paths …

We consider the evaluation of first-order queries over classes of databases that are nowhere
dense. The notion of nowhere dense classes was introduced by Nesetril and Ossona de …

We investigate the query evaluation problem for fixed queries over fully dynamic databases,
where tuples can be inserted or deleted. The task is to design a dynamic algorithm that …

Tractability results for the model checking problem of logics yield powerful algorithmic meta
theorems of the form: Every computational problem expressible in a logic $ L $ can be …

The disjoint paths logic, FOL+ DP, is an extension of First-Order Logic (FOL) with the extra
atomic predicate dp k (x 1, y 1,…, xk, yk), expressing the existence of internally vertex …

In the logical framework introduced by Grohe and Tur\'an (TOCS 2004) for Boolean
classification problems, the instances to classify are tuples from a logical structure, and …

We propose an algebraic framework for studying efficient algorithms for query evaluation,
aggregation, enumeration, and maintenance under updates, on sparse databases. Our …

Given ak-node pattern graph H and an n-node host graph G, the subgraph counting problem
asks to compute the number of copies of H in G. In this work we address the following …

It is known that first-order logic with some counting extensions can be efficiently evaluated
on graph classes with bounded expansion, where depth-$ r $ minors have constant density …