Concept

Max-flow min-cut theorem

Related publications (106)

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.

Combinatorial algorithms for wireless information flow

Christina Fragouli, Aurore Amaudruz

A long-standing open question in information theory is to characterize the unicast capacity of a wireless relay network. The difficulty arises due to the complex signal interactions induced in the network, since the wireless channel inherently broadcasts t ...

2009

Multiline Addressing by Network Flow

Friedrich Eisenbrand

We consider an optimization problem arising in the design of controllers for OLED displays. Our objective is to minimize amplitude of the electrical current through the diodes which has a direct impact on the lifetime of such a display. Modeling the proble ...

2009

On the Capacity of Non-Coherent Network Coding

Mahdi Jafari, Christina Fragouli, Suhas Diggavi

The min-cut value towards a single receiver in a network with unit capacity edges can be achieved by routing a single bit. The multicast theorem in network coding shows that, the common min-cut value towards N >= 1 receivers can also be achieved using pack ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

A note on the data-driven capacity of P2P networks

Pascal Frossard

We consider two capacity problems in P2P networks. In the first one, the nodes have an infinite amount of data to send and the goal is to optimally allocate their uplink bandwidths such that the demands of every peer in terms of receiving data rate are met ...

2009

Code Construction for Multiple Sources Network Coding

Christina Fragouli, Suhas Diggavi

In several wireless applications multiple sources transmit information to one or more receivers, many times over unknown topologies. This is especially so in mobile networks where learning the topology may have prohibitive complexity. Network coding techni ...

Acm Order Department, P O Box 64145, Baltimore, Md 21264 Usa2009

Branch and Price for the Vehicle Routing Problem with Discrete Split Deliveries and Time Windows

Matteo Salani, Ilaria Vacca

The Discrete Split Delivery Vehicle Routing Problem with Time Windows (DSDVRPTW) consists of designing the optimal set of routes to serve, at least cost, a given set of customers while respecting constraints on vehicles capacity and customer time windows. ...

2009

Semi-Supervised Segmentation based on Non-local Continuous Min-Cut

Jean-Philippe Thiran, Xavier Bresson, Nawal Houhou

We propose a semi-supervised image segmentation method that relies on a non-local continuous version of the min-cut algorithm and labels or seeds provided by a user. The segmentation process is performed via energy minimization. The proposed energy is comp ...

Springer2009

Actin-myosin viscoelastic flow in the keratocyte lamellipod

Maxime Fred Maurice Fournier, Alex Mogilner

The lamellipod, the locomotory region of migratory cells, is shaped by the balance of protrusion and contraction. The latter is the result of myosin-generated centripetal flow of the viscoelastic actin network. Recently, quantitative flow data was obtained ...

2009

A distributed minimum-distortion routing algorithm with in-network data processing

Ramin Khalili

In many wired and wireless networks, nodes process input traffic to satisfy a network constraint (e.g., a capacity constraint) and to increase the utility of data in the output flows given these constraints. In this paper we focus on the special case in wh ...

2008

Structural Efficiency of Percolated Landscapes in Flow Networks

Paolo De Los Rios

The large-scale structure of complex systems is intimately related to their functionality and evolution. In particular, global transport processes in flow networks rely on the presence of directed pathways from input to output nodes and edges, which organi ...

Public Library of Science2008