Publications (PhD and after)

Source identification via contact tracing in the presence of asymptomatic patients Permalink

Gergely Ódor, Jana Vuckovic, Miguel-Angel Sanchez Ndoye, Patrick Thiran

Published in Applied Network Science, 2023

One sentence abstract:

We define and prove rigorous results about a new source identification framework, where the network is initially not known to the algorithm, but must be explored through queries (similarly to the node infection times), and we evaluate our algorithms on realistic datasets.

Switchover phenomenon for general graphs Permalink

Dániel Keliger, László Lovász, Tamás Móri and Gergely Ódor

Published in arxiv, 2023

One sentence abstract:

We rigorously prove the existence of the switchover phenomenon claim under mild, deterministic assumptions on the underlying graph.

On the robustness of the metric dimension of grid graphs to adding a single edge Permalink

Satvik Mashkaria, Gergely Ódor, Patrick Thiran

Published in Discrete Applied Mathematics, 2022

One sentence abstract:

We prove that if we add an extra edge to a (large enough) d-dimensional grid graph, then the resulting graph will have metric dimension between d and 2d, and we almost completely settle the case for d=2.

The power of adaptivity in source identification with time queries on the path Permalink

Victor Lecomte, Gergely Ódor, and Patrick Thiran

Published in Theoretical Computer Science, 2022

One sentence abstract:

We provide the first theoretical results on the query complexity of the source identification problem when queried nodes report their infection time; in the adaptive case we need only Θ(loglog(n)) queries, while in the non-adaptive case Θ(n) queries are needed.

Sequential metric dimension for random graphs Permalink

Gergely Ódor and Patrick Thiran

Published in Journal of Applied Probability, 2021

One sentence abstract:

We prove that the sequential version of the metric dimension (where the landmarks can be chosen adaptively to distinguish every pair of nodes based on distances) is only a multiplicative constant factor smaller than the (non-adaptive) metric dimension in Erdos-Renyi graphs

Switchover phenomenon induced by epidemic seeding on geometric networks Permalink

Gergely Ódor, Domonkos Czifra, Júlia Komjáthy, László Lovász, Márton Karsai

Published in Proceedings of the National Academy of Sciences, 2021

One sentence abstract:

We observe empirically and prove theoretically a new phenomenon related to how the initial seeding affects the outcome of an epidemic.

Metric dimension of critical Galton-Watson trees and linear preferential attachment trees Permalink

Júlia Komjáthy, Gergely Ódor

Published in European Journal of Combinatorics, 2021

One sentence abstract:

Building on the literature of fringe trees, we prove law of large numbers type results for the metric dimension of various random trees.