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

DOI10.1016/J.TCS.2022.02.008MaRDI QIDQ2118878zbMATH OpenOpenAlexFDO

Authors Victor Lecomte, Gergely Ódor, Patrick Thiran

Publication date 23 March 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.tcs.2022.02.008

zbMATH Keywords

lower boundsgraph algorithmsnoisy informationsource location

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Source detection on graphs
• Finding rumor sources on random trees
• Epicenter of random epidemic spanning trees on finite graphs
• Locating the contagion source in networks with partial timestamps
• Multiple propagation paths enhance locating the source of diffusion in complex networks

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3494441 (Why is no real title available?)
• scientific article; zbMATH DE number 3205803 (Why is no real title available?)
• A sequential locating game on graphs
• Active learning
• An adaptivity hierarchy theorem for property testing
• Approximability of the minimum weighted doubly resolving set problem
• Computing with Noisy Information
• Deterministic and probabilistic binary search in graphs
• Emergence of Scaling in Random Networks
• Finding Adam in random growing trees
• Fourier analysis of distribution functions. A mathematical study of the Laplace-Gaussian law
• How close is the sample covariance matrix to the actual covariance matrix?
• Identifying codes and searching with balls in graphs
• Limiting geodesics for first-passage percolation on subsets of \(\mathbb{Z}^{2}\)
• Locating the contagion source in networks with partial timestamps
• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Networks
• Noisy binary search and its applications
• On the limiting distribution of the metric dimension for random forests
• Random Geometric Graphs
• Resolution Limits for the Noisy Non-Adaptive 20 Questions Problem
• Rumors in a Network: Who's the Culprit?
• Sequential metric dimension for random graphs
• The Accuracy of the Gaussian Approximation to the Sum of Independent Variates

Cited in

(1)

• Sharp bound on the truncated metric dimension of trees

This page was built for publication: The power of adaptivity in source identification with time queries on the path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2118878)