Publications related to Steiner tree problem

Optimal design of observable multi-agent networks: A structural system approach

Colin Neil Jones, Francisco Fernandes Castro Rego

This paper introduces a method to design observable directed multi-agent networks, that are: 1) either minimal with respect to a communications-related cost function, or 2) idem, under possible failure of direct communication between two agents. An observa ...

2014

Optimal Design of Observable Multi-Agent Networks: A Structural System Approach

Colin Neil Jones, Francisco Fernandes Castro Rego

IEEE2014

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

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Serge Vaudenay, Alexandre Raphaël Duc

We propose HELEN, a code-based public-key cryptosystem whose security is based on the hardness of the Learning from Parity with Noise problem (LPN) and the decisional minimum distance problem. We show that the resulting cryptosystem achieves indistinguisha ...

Springer2013

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic

Location privacy is a major concern in pervasive networks where static device identifiers enable malicious eavesdroppers to continuously track users and their movements. In order to prevent such identifier-based tracking, devices could coordinate regular i ...

2013

Stable Routing And Unique-Max Coloring On Trees

Laura Sanità, Rico Zenklusen

Some of the routing protocols used in telecommunication networks route traffic on a shortest path tree according to configurable integral link weights. One crucial issue for network operators is finding a weight function that ensures a stable routing: when ...

Siam Publications2013

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Dominique de Werra, Bernard Ries

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGS ...

2012

Pliable Index Coding

Christina Fragouli, Siddhartha Brahma

We propose a new formulation of the index coding problem, where instead of demanding a specific message, clients are “pliable” and are happy to receive any one message they do not have. We prove that with this relaxation, although some instances of this pr ...

Ieee2012

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.

Steiner tree problem

Optimal design of observable multi-agent networks: A structural system approach

Optimal Design of Observable Multi-Agent Networks: A Structural System Approach

Steiner Tree Approximation via Iterative Randomized Rounding

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

Stable Routing And Unique-Max Coloring On Trees

Damage predicting algorithms for regular RC structures

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Pliable Index Coding

Graph Chatbot

Chat with Graph Search

Steiner Tree Approximation via Iterative Randomized Rounding

Optimal design of observable multi-agent networks: A structural system approach

Optimal Design of Observable Multi-Agent Networks: A Structural System Approach

Damage predicting algorithms for regular RC structures

HELEN: A Public-Key Cryptosystem Based on the LPN and the Decisional Minimal Distance Problems

Pliable Index Coding

Optimizing Mix-zone Coverage in Pervasive Wireless Networks

d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Stable Routing And Unique-Max Coloring On Trees