Concept

Shortest path problem

Related publications (252)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Dynamic Quantification of the Effect of Traffic Congestion on a Multilayer Network

The paper “Dynamic efficiency in multilayer transportation networks” (Bellocchi, Geroliminis, 2018) [1] introduced new performance measures to quantify dynamically the effect of traffic congestion in a multilayer network. Based on these measures, we explor ...

2020

Optimized path planning of a swarm of drones for massive data collection

This Master project is part of laboratory research consisting in optimizing path planning of a swarm of drones for massive traffic data collection. The main goals aim to determine the optimal number of drones to use given the available fleet and to generat ...

2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Specular Manifold Sampling for Rendering High-Frequency Caustics and Glints

Wenzel Alban Jakob, Tizian Lucien Zeltner

Scattering from specular surfaces produces complex optical effects that are frequently encountered in realistic scenes: intricate caustics due to focused reflection, multiple refraction, and high-frequency glints from specular microstructure. Yet, despite ...

ASSOC COMPUTING MACHINERY2020

Flooding And Diameter In General Weighted Random Graphs

Thomas Mountford, Jacques Saliba

In this paper we study first passage percolation on a random graph model, the configuration model. We first introduce the notions of weighted diameter, which is the maximum of the weighted lengths of all optimal paths between any two vertices in the graph, ...

CAMBRIDGE UNIV PRESS2020

Numerical Approximation Of Orthogonal Maps

Marco Picasso, Alexandre Caboussat, Dimitrios Gourzoulidis

Orthogonal maps are the solutions of the mathematical model of paper-folding, also called the origami problem. They consist of a system of first-order fully nonlinear equations involving the gradient of the solution. The Dirichlet problem for orthogonal ma ...

2019

Memory Efficient Max Flow for Multi-Label Submodular MRFs

Mathieu Salzmann

Multi-label submodular Markov Random Fields (MRFs) have been shown to be solvable using max-flow based on an encoding of the labels proposed by Ishikawa, in which each variable X-i is represented by l nodes (where l is the number of labels) arranged in a c ...

2019

Extrapolating Paths with Graph Neural Networks

Andreas Loukas, Jean-Baptiste Francis Marie Juliette Cordonnier

We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the int ...

IJCAI, Inc.2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

Quantifying bacterial structure of aerobic granular sludge using image analysis

Karen Gemayel

This Master’s project entitled ’Quantifying Bacterial Structure of Aerobic Granular Sludge using Image Analysis’ aims to quantitatively describe various aspects of cell activity inside aerobic granular sludge using image analysis. It entails the theory of ...

2019