Euclidean minimum spanning tree

Formal sciences
Theoretical computer science
Algorithms and data structures
Computational geometry

About
Privacy
Disclaimer

Graph Chatbot

Related publications (29)

Optimal Software Patching Plan for PMUs

Jean-Yves Le Boudec, Ola Nils Anders Svensson, Teklemariam Tsegay Tesfay

Phasor measurement units (PMUs) deployed to monitor the state of an electrical grid need to be patched from time to time to prevent attacks that exploit vulnerabilities in the software. Applying some of these patches requires a PMU reboot, which takes the ...

2017

Exponential extinction time of the contact process on finite graphs

Thomas Mountford, Daniel Rodrigues Valesin, Jean-Christophe Mourrat

We study the extinction time tau of the contact process started with full occupancy on finite trees of bounded degree. We show that, if the infection rate is larger than the critical rate for the contact process on Z, then, uniformly over all trees of degr ...

Elsevier Science Bv2016

Inhomogeneous minima of mixed signature lattices

Eva Bayer Fluckiger, Martino Borello, Peter Simon Jossen

We establish an explicit upper bound for the Euclidean minimum of a number field which depends, in a precise manner, only on its discriminant and the number of real and complex embeddings. Such bounds were shown to exist by Davenport and Swinnerton-Dyer ([ ...

Academic Press Inc Elsevier Science2016

ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications

Rachid Guerraoui, Aleksandar Dragojevic, Georgios Chatzopoulos

This paper presents ESTIMA, an easy-to-use tool for extrapolating the scalability of in-memory applications. ESTIMA is designed to perform a simple, yet important task: given the performance of an application on a small machine with a handful of cores, EST ...

ACM Press2016

Living on the Edge: Re-shaping the Interface of Synthetic Biology and Nanotechnology

Ardemis Anoush Boghossian, Shang-Jung Wu

A new team of researchers at EPFL is taking an 'anti-disciplinary' approach to creating optical devices. These devices take advantage of the synergy in tuning both nano- and bio-material properties, coupling 'the advantages of two growing, albeit tradition ...

Schweizerische Chemische Gesellschaft2016

Downsampling of Signals on Graphs Via Maximum Spanning Trees

Quy Ha Nguyen, Minh Do

Downsampling of signals living on a general weighted graph is not as trivial as of regular signals where we can simply keep every other samples. In this paper we propose a simple, yet effective downsampling scheme in which the underlying graph is approxima ...

Ieee-Inst Electrical Electronics Engineers Inc2015

Enforcing Efficient Equilibria in Network Design Games via Subsidies

Christos Kalaitzis

The efficient design of networks has been an important engineering task that involves challenging combinatorial optimization problems. Typically, a network designer has to select among several alternatives which links to establish so that the resulting net ...

Springer Verlag2015

Sparse Group Covers and Greedy Tree Approximations

Volkan Cevher, Luca Baldassarre

We consider the problem of finding a K-sparse approximation of a signal, such that the support of the approximation is the union of sets from a given collection, a.k.a. group structure. This problem subsumes the one of finding K-sparse tree approximations. ...

2015

Improving Christofides' Algorithm for the s-t Path TSP

Hyung Chan An

We present a deterministic (1+root 5/2)-approximation algorithm for the s-t path TSP for an arbitrary metric. Given a symmetric metric cost on n vertices including two prespecified endpoints, the problem is to find a shortest Hamiltonian path between the t ...

Assoc Computing Machinery2015

Page 2 of 2