Concept

Widest path problem

Related publications (31)

Faster 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 Informatik2021

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

Biomimetic adaptive control of a deployable tensegrity structure

Ann Christine Sychterz

Biomimetic behavior includes aspects such as learning from previous experience, self-diagnosis, and adaptation. This thesis describes control methodologies that are essential to development towards biomimetic behavior of a complex deployable structure. Sim ...

EPFL2018

Fréchet means in Wasserstein space

Yoav Zemel

This work studies the problem of statistical inference for Fréchet means in the Wasserstein space of measures on Euclidean spaces,

\mathcal W_2 ( \mathbb R^d )

. This question arises naturally from the problem of separating amplitude and phase variation i ...

EPFL2017

Real-Time Optimization via Directional Modifier Adaptation, with Application to Kite Control

Sean Costello

The steady advance of computational methods makes model-based optimization an increasingly attractive method for process improvement. Unfortunately, the available models are often inaccurate. The traditional remedy is to update the model parameters, but th ...

EPFL2015

Improving Christofides' Algorithm for the s-t Path TSP

Hyung Chan An

We present a deterministic (1+root 5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the t ...

Assoc Computing Machinery2015

Cooperative and competitive spreading dynamics on the human connectome

Alessandra Griffa, Patric Hagmann, Olaf Sporns

Increasingly detailed data on the network topology of neural circuits create a need for theoretical principles that explain how these networks shape neural communication. Here we use a model of cascade spreading to reveal architectural features of human br ...

Cell Press2015

Joint Power Allocation and Path Selection for Multi-Hop Noncoherent Decode and Forward UWB Communications

Xiaoli Ma, Marco Mondelli, Qi Zhou

With the aim of extending the coverage and improving the performance of impulse radio ultra-wideband (UWB) systems, this paper focuses on developing a novel single differential encoded decode and forward (DF) non-cooperative relaying scheme (NCR). To favor ...

Ieee-Inst Electrical Electronics Engineers Inc2014

Seam Carving for Text Line Extraction on Color and Grayscale Historical Manuscripts

Sabine Süsstrunk, Nikolaos Arvanitopoulos Darginis

We propose a novel algorithm for automatic text line extraction on color and grayscale manuscript pages without prior binarization. Our algorithm is based on seam carving to compute separating seams between text lines. Seam carving is likely to produce ...

2014

Tracing path-guided apparent motion in human primary visual cortex V1

Michael Herzog, Michel Akselrod

Vision is a constructive process. For example, a square, flashed at two distinct locations one after the other, appears to move smoothly between the two locations rather than as two separate flashes (apparent motion). Apparent motion is usually perceived a ...

Nature Publishing Group2014

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.

Fréchet means in Wasserstein space

Yoav Zemel

This work studies the problem of statistical inference for Fréchet means in the Wasserstein space of measures on Euclidean spaces,

\mathcal W_2 ( \mathbb R^d )

. This question arises naturally from the problem of separating amplitude and phase variation i ...

EPFL2017