Publication
The Role of Adaptivity in Source Identification with Time Queries
Publications associées (36)
Relative, local and global dimension in complex networks
Dimension is a fundamental property of objects and the space in which they are embedded. Yet ideal notions of dimension, as in Euclidean spaces, do not always translate to physical spaces, which can be constrained by boundaries and distorted by inhomogenei ...
NATURE PORTFOLIO2022Sequential metric dimension for random graphs
In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...
2021Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021Cluster-and-Conquer: When Randomness Meets Graph Locality
Anne-Marie Kermarrec, Olivier Ruas
K-Nearest-Neighbors (KNN) graphs are central to many emblematic data mining and machine-learning applications. Some of the most efficient KNN graph algorithms are incremental and local: they start from a random graph, which they incrementally improve by tr ...
IEEE COMPUTER SOC2021Switchover phenomenon induced by epidemic seeding on geometric networks
It is a fundamental question in disease modeling how the initial seeding of an epidemic, spreading over a network, determines its final outcome. One important goal has been to find the seed configuration, which infects the most individuals. Although the id ...
2021Actuator Placement under Structural Controllability using Forward and Reverse Greedy Algorithms
Maryam Kamgarpour, Tyler Summers, Baiwei Guo, Orcun Karaca
Actuator placement is an active field of research which has received significant attention for its applications in complex dynamical networks. In this paper, we study the problem of finding a set of actuator placements minimizing the metric that measures t ...
2020New Graph Algorithms via Polyhedral Techniques
In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...
EPFL2019Alignment and Assembly
Over recent years, many large network datasets become available, giving rise to novel and valuable applications of data mining and machine learning techniques. These datasets include social networks, the structure of the Internet, and protein-interaction n ...
EPFL2017Vertex-Frequency Analysis on Graphs
Pierre Vandergheynst, Benjamin Ricaud, David Shuman
One of the key challenges in the area of signal processing on graphs is to design dictionaries and transform methods to identify and exploit structure in signals on weighted graphs. To do so, we need to account for the intrinsic geometric structure of the ...
Academic Press Inc Elsevier Science2016Network Alignment: Theory, Algorithms, and Applications
Networks are central in the modeling and analysis of many large-scale human and technical systems, and they have applications in diverse fields such as computer science, biology, social sciences, and economics. Recently, network mining has been an active a ...
EPFL2016