Publication

Node-weighted network design and maximum sub-determinants

Related publications (208)

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.

Circular Ones Matrices and the Stable set Polytopes of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

It is a long standing open problem to find an explicit description of the stable set polytope of claw-free graphs. Yet more than 20 years after the discovery of a polynomial algorithm for the maximum stable set problem for claw-free graphs, there is even n ...

2005

New approaches for virtual private network design

Friedrich Eisenbrand

Virtual private network design is the following NP-hard problem. We are given a communication network, represented as a weighted graph with thresholds on the nodes which represent the amount of flow that a node can send to and receive from the network. The ...

2005

Disassembly scheduling

Hwa-Joong Kim

This dissertation focuses on disassembly scheduling, which is the problem of determining the quantity and timing of disassembling used or end-of-life products while satisfying the demand of their parts/components over a given planning horizon. The objectiv ...

EPFL2005

Computing All Faces of the Minkowski Sum of V-Polytopes

Christophe Weibel

We consider the problem of listing faces of the Minkowski sum of several V-polytopes in R^d. An algorithm for listing all faces of dimension up to j is presented, for any given 0

2005

A Scalable Method for Multiagent Constraint Optimization

Boi Faltings, Adrian Petcu

We present in this paper a new complete method for distributed constraint optimization. This is a utility-propagation method, inspired by the sum-product algorithm (Kschischang et al 2001). The original algorithm requires fixed message sizes, linear memory ...

2005

Some combinatorial optimization problems in graphs with applications in telecommunications and tomography

David Schindl

The common point between the different chapters of the present work is graph theory. We investigate some well known graph theory problems, and some which arise from more specific applications. In the first chapter, we deal with the maximum stable set probl ...

EPFL2004

Active measurement for multiple link failure diganosis in IP networks

Patrick Thiran, Xuan Hung Nguyen

Simultaneous link failures are common in IP networks \cite{Markopoulou04}. In this paper, we develop a technique for locating multiple failures in Service Provider or Enterprise IP networks using active measurement. We propose a two-phased approach that mi ...

2004

Circular Ones Matrices and the Stable Set Polytope of Quasi-Line Graphs

Friedrich Eisenbrand, Gautier Stauffer

2004

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

In this paper, we consider the minimization of a relevant energy consumption related cost function in the context of sensor networks where correlated sources are generated at various sets of source nodes and have to be transmitted to some set of sink nodes ...

Springer Verlag2004

Networked Slepian-Wolf: Theory and Algorithms

Martin Vetterli, Razvan Cristescu

2004