Publications related to Shortest path problem

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

2023

Localizing Traffic Differentiation

Pavlos Nikolopoulos, Muhammad Abdullah, Zeinab Shmeis

Network neutrality is important for users, content providers, policymakers, and regulators interested in understanding how network providers differentiate performance. When determining whether a network differentiates against certain traffic, it is importa ...

2023

Finding Paths for Explainable MOOC Recommendation: A Learner Perspective

Jibril Albachir Frej, Tatjana Nazaretsky

The increasing availability of Massive Open Online Courses (MOOCs) has created a necessity for personalized course recommendation systems. These systems often combine neural networks with Knowledge Graphs (KGs) to achieve richer representations of learners ...

2023

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

Patrick Thiran, Gergely Odor, Victor Cyril L Lecomte

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, ...

2022

The Role of Adaptivity in Source Identification with Time Queries

Gergely Odor

Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final siz ...

EPFL2022

Order parameters for antiferromagnetic structures: A first-principles study of iridium manganese

Anirudh Raju Natarajan

We use density-functional theory to study the ordered states of iridium manganese, demonstrating a simple but powerful method for describing magnetic structures and the transitions among them. As an illustrative example, the coupling of magnetism and cryst ...

AMER PHYSICAL SOC2022

WEBGRAPH: Capturing Advertising and Tracking Information Flows for Robust Blocking

Carmela González Troncoso, Sandra Deepthy Siby

Users rely on ad and tracker blocking tools to protect their privacy. Unfortunately, existing ad and tracker blocking tools are susceptible to mutable advertising and tracking content. In this paper, we first demonstrate that a state-of-the-art ad and trac ...

USENIX ASSOC2022

Paying for negative emissions

Philippe Thalmann

Negative emissions are necessary on the path to net-zero. This short presentation shows how they contribute to climate neutrality and how that could be paid for. ...

2022

One Fuzz Doesn’t Fit All: Optimizing Directed Fuzzing via Target-tailored Program State Restriction

Mathias Josef Payer

Fuzzing is the de-facto default technique to discover software flaws, randomly testing programs to discover crashing test cases. Yet, a particular scenario may only care about specific code regions (for, e.g., bug reproduction, patch or regression testing) ...

ASSOC COMPUTING MACHINERY2022

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

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 Informatik2021

Shortest path problem

Graph Chatbot

Chat with Graph Search

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Localizing Traffic Differentiation

Finding Paths for Explainable MOOC Recommendation: A Learner Perspective

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

The Role of Adaptivity in Source Identification with Time Queries

Order parameters for antiferromagnetic structures: A first-principles study of iridium manganese

WEBGRAPH: Capturing Advertising and Tracking Information Flows for Robust Blocking

Paying for negative emissions

One Fuzz Doesn’t Fit All: Optimizing Directed Fuzzing via Target-tailored Program State Restriction

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Finding Paths for Explainable MOOC Recommendation: A Learner Perspective

Localizing Traffic Differentiation

WEBGRAPH: Capturing Advertising and Tracking Information Flows for Robust Blocking

Order parameters for antiferromagnetic structures: A first-principles study of iridium manganese

Paying for negative emissions

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

The Role of Adaptivity in Source Identification with Time Queries

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

One Fuzz Doesn’t Fit All: Optimizing Directed Fuzzing via Target-tailored Program State Restriction