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.

On the Impact of Uncertainty for Path Planning

We consider the problem of planning paths on graphs with some edges whose traversability is uncertain; for each uncertain edge, we are given a probability of being traversable (e.g., by a learned classifier). We categorize different interpretations of the ...

2019

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash, Osman Emre Dai

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

Online Matching with General Arrivals

Ola Nils Anders Svensson, Mikhail Kapralov, Buddhima Ruwanmini Gamlath Gamlath Ralalage, Andreas Maggiori, David Wajc

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

IEEE COMPUTER SOC2019

Semiclassical analysis of the quantum instanton approximation

Jiri Vanicek, Christophe Louis Joseph Jean-Luc Vaillant

We explore the relation between the quantum and semiclassical instanton approximations for the reaction rate constant. From the quantum instanton expression, we analyze the contributions to the rate constant in terms of minimum-action paths and find that t ...

2019

More Results on Shortest Linear Programs

Subhadeep Banik

At the FSE conference of ToSC 2018, Kranz et al. presented their results on shortest linear programs for the linear layers of several well known block ciphers in literature. Shortest linear programs are essentially the minimum number of 2-input xor gates r ...

2019

Evo-Bots: A Simple, Stochastic Approach to Self-assembling Artificial Organisms

Francesco Mondada, Roderich Gross

This paper describes an alternative path towards artificial life-one by which simple modular robots with novel hybrid motion control are used to represent artificial organisms. We outline conceptually how such a system would work, and present a partial har ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

Edge Ordered Turan Problems

Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

COMENIUS UNIV2019

SBFT: a Scalable and Decentralized Trust Infrastructure

Dragos-Adrian Seredinschi

SBFT is a state of the art Byzantine fault tolerant state machine replication system that addresses the challenges of scalability, decentralization and global geo-replication. SBFT is optimized for decentralization and is experimentally evaluated on a depl ...

IEEE COMPUTER SOC2019

rDAN: Toward robust demand-aware network designs

Andreas Loukas

We currently witness the emergence of interesting new network topologies optimized towards the traffic matrices they serve, such as demand-aware datacenter interconnects (eg, ProjecToR) and demand-aware peer-to-peer overlay networks (eg, SplayNets). This p ...

2018

Constant factor approximation for ATSP with two edge weights

Ola Nils Anders Svensson, Jakub Tarnawski

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was give ...

SPRINGER HEIDELBERG2018