Concept
Steiner tree problem
Related publications (102)
HELEN: a Public-key Cryptosystem Based on the LPN Problem (Extended Abstract)
Serge Vaudenay, Alexandre Raphaël Duc
We propose HELEN, a new 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 indistingu ...
2012Orthogeodesic Point-Set Embedding of Trees
Radoslav Fulek, Fabrizio Frati
Let S be a set of N grid points in the plane, no two of which lie on the same horizontal or vertical line, and let G be a graph with n vertices (n
Elsevier Science Bv2011Primal-dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs
NODE-WEIGHTED STEINER FOREST is the following problem: Given an undirected graph, a set of pairs of terminal vertices, a weight function on the vertices, find a minimum weight set of vertices that includes and connects each pair of terminals. We consider t ...
Academic Press Inc Elsevier Science2011Maximum likelihood estimation for multiple-source losss tomography with network coding
Loss tomography aims at inferring the loss rate of links in a network from end-to-end measurements. Previous work in [1] has developed optimal maximum likelihood estimators (MLEs) for link loss rates in a single-source multicast tree. However, only sub-opt ...
2011Optimizing Mixing in Pervasive Networks: A Graph-Theoretic Perspective
Jean-Pierre Hubaux, Murtuza Jadliwala, Igor Bilogrevic
One major concern in pervasive wireless applications is location privacy, where malicious eavesdroppers, based on static device identifiers, can continuously track users. As a commonly adopted countermeasure to prevent such identifier-based tracking, devic ...
Springer2011Content Search Through Comparisons
We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a problem strongly related to small-world network design. We show that, under heterogeneous demand, the small-world network design proble ...
2011Content Search Through Comparisons
We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a prob- lem strongly related to small-world network design. We show that, under heterogeneous demand, the small-world network design prob ...
2011Adaptive Content Search Through Comparisons
We study the problem of navigating through a database of similar objects using comparisons. This problem is known to be strongly related to the small-world network design problem. However, contrary to prior work, which focuses on cases where objects in the ...
Massachusetts Institute of Technology Press2011Energy-Proportional and Scalable Networks
The power consumption of the Internet and datacenter networks is already significant due to a large degree of redundancy and high idle power consumption of the network elements. Therefore, dynamically matching network resources to the actual load is highly ...
EPFL2011Geodesic Active Fields - A Geometric Framework for Image Registration
Jean-Philippe Thiran, Xavier Bresson, Dominique Zosso
In this paper we present a novel geometric framework called geodesic active fields for general image registration. In image registration, one looks for the underlying deformation field that best maps one image onto another. This is a classic ill-posed inve ...
Institute of Electrical and Electronics Engineers2011