Concept

Path (graph theory)

Related publications (175)

Microsimulation Framework for Urban Price-Taker Markets

In the context of integrated transportation and other urban engineering infrastructure systems, there are many examples of markets, where consumers exhibit price-taking behaviour. While this behaviour is ubiquitous, the underlying mechanism can be captured ...

2013

Graph theory reveals dysconnected hubs in 22q11DS and altered nodal efficiency in patients with hallucinations

Jean-Philippe Thiran, Leila Cammoun, Marie Schaer

Schizophrenia is postulated to be the prototypical dysconnection disorder, in which hallucinations are the core symptom. Due to high heterogeneity in methodology across studies and the clinical phenotype, it remains unclear whether the structural brain dys ...

Frontiers Research Foundation2013

Extreme prematurity and intra uterine growth restriction effects in brain network topology at school age

Jean-Philippe Thiran, Elda Fischi Gomez, Djalel Eddine Meskaldji, François Lazeyras

Higher risk for long-term behavioral and emotional sequelae, with attentional problems (with or without hyperactivity) is now becoming one of the hallmarks of extreme premature (EP) birth and birth after pregancy conditions leading to poor intra uterine gr ...

2013

Inference of Mobility Patterns via Spectral Graph Wavelets

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Modern data processing tasks frequently involve structured data, for example signals defined on the vertex set of a weighted graph. In this paper, we address the problem of inference of mobility patterns from data defined on geographical graphs based on sp ...

2013

On the Sparsity of Wavelet Coefficients for Signals on Graphs

Pierre Vandergheynst, Benjamin Ricaud, David Shuman

A number of new localized, multiscale transforms have recently been introduced to analyze data residing on weighted graphs. In signal processing tasks such as regularization and compression, much of the power of classical wavelets on the real line is deriv ...

Spie-Int Soc Optical Engineering2013

Segmenting Planar Superpixel Adjacency Graphs w.r.t. Non-planar Superpixel Affinity Graphs

Engin Türetken

We address the problem of segmenting an image into a previously unknown number of segments from the perspective of graph partitioning. Specifically, we consider minimum multicuts of superpixel affinity graphs in which all affinities between non-adjacent su ...

2013

Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back

Aleksander Madry

We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...

IEEE2013

Steiner Tree Approximation via Iterative Randomized Rounding

Thomas Rothvoss, Laura Sanità

The Steiner tree problem is one of the most fundamental NP-hard problems: given a weighted undirected graph and a subset of terminal nodes, find a minimum-cost tree spanning the terminals. In a sequence of papers, the approximation ratio for this problem w ...

Assoc Computing Machinery2013

Optimization-based solutions to constrained trajectory-tracking and path-following problems

Timm Faulwasser

The prototypical problem in control theory is the stabilization of a set point. When, instead of a set point, a time-varying reference needs to be stabilized, then the problem is called trajectory tracking. Typical examples of trajectory-tracking problems ...

Shaker Verlag2013

Scalable Routing Easy as PIE: a Practical Isometric Embedding Protocol (Technical Report)

Patrick Thiran, Julien Pierre Sacha Herzen

We present PIE, a scalable routing scheme that achieves 100% packet delivery and low path stretch. It is easy to implement in a distributed fashion and works well when costs are associated to links. Scalability is achieved by using virtual coordinates in a ...

2013

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.