Concept

Problème de plus court chemin

Publications associées (252)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

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