Publications related to Euclidean minimum spanning tree

Decomposition method to evaluate district heating/cooling network potential at urban scale

François Maréchal, Luc Girardin, Ana Catarina Gouveia Braz, Bingqian Liu, Raphaël Briguet

In this work, a tool to design district heating networks (DHN) is presented and applied to the city of Lausanne as a case study. The evaluation of the buildings’ heat/cooling demand is performed using a Geographic Information System (GIS) database, built f ...

Associazione Italiana Di Ingegneria Chimica2024

Distributed Optimization with Byzantine Robustness Guarantees

Lie He

As modern machine learning continues to achieve unprecedented benchmarks, the resource demands to train these advanced models grow drastically. This has led to a paradigm shift towards distributed training. However, the presence of adversariesâ whether ma ...

EPFL2023

Spectral Hypergraph Sparsifiers of Nearly Linear Size

Mikhail Kapralov, Jakab Tardos

Graph sparsification has been studied extensively over the past two decades, culminating in spectral sparsifiers of optimal size (up to constant factors). Spectral hypergraph sparsification is a natural analogue of this problem, for which optimal bounds on ...

IEEE COMPUTER SOC2022

Scaling theory for the statistics of slip at frictional interfaces

Matthieu Wyart, Thomas Willem Jan de Geus

Slip at a frictional interface occurs via intermittent events. Understanding how these events are nucleated, can propagate, or stop spontaneously remains a challenge, central to earthquake science and tribology. In the absence of disorder, rate-and-state a ...

AMER PHYSICAL SOC2022

Minimal graphs for 2-factor extension

Dominique de Werra

Let G = (V, E) be a simple loopless finite undirected graph. We say that G is (2-factor) expandable if for any non-edge uv, G + uv has a 2-factor F that contains uv. We are interested in the following: Given a positive integer n = vertical bar V vertical b ...

ELSEVIER2020

Exceptional graphs for the random walk

Juhan Aru

If W is the simple random walk on the square lattice Z(2), then W induces a random walk W-G on any spanning subgraph G subset of Z(2) of the lattice as follows: viewing W as a uniformly random infinite word on the alphabet {x, -x, y, -y}, the walk W-G star ...

INST MATHEMATICAL STATISTICS2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

The Complexity of Self-Dual Monotone 7-Input Functions

Giovanni De Micheli, Mathias Soeken, Eleonora Testa, Winston Jason Haaswijk

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 i ...

2019

Saturation of Berge hypergraphs

Abhishek Methuku

Given a graph F, a hypergraph is a Berge-F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge-F-saturated if H does not contain a subhypergraph that is a Berge-F, but for any edge e is an element of E((H ...

Elsevier2019

Prism-based path set restriction for solving Markovian traffic assignment problem

Yuki Oyama

This paper deals with a main limitation of Markovian traffic assignment (MTA) models: when the network includes cyclic structures and the link costs are small enough, the fact that the MTA models assign traffic flows to all feasible paths causes computatio ...

Elsevier2019

Weighted Matchings via Unweighted Augmentations

Ola Nils Anders Svensson, Slobodan Mitrovic, Buddhima Ruwanmini Gamlath Gamlath Ralalage

We design a generic method to reduce the task of finding weighted matchings to that of finding short augmenting paths in unweighted graphs. This method enables us to provide efficient implementations for approximating weighted matchings in the massively pa ...

ASSOC COMPUTING MACHINERY2019

Approximating the rectilinear crossing number

János Pach

A straight-line drawing of a graph G is a mapping which assigns to each vertex a point in the plane and to each edge a straight-line segment connecting the corresponding two points. The rectilinear crossing number of a graph G, (cr) over bar (G), is the mi ...

2019

Approximating Steiner trees and forests with minimum number of Steiner points

Nachshon Cohen

Let R be a finite set of terminals in a convex metric space (M, d). We give approximation algorithms for problems of finding a minimum size set S subset of M of additional points such that the unit-disc graph G[R boolean OR S] of R boolean OR S satisfies s ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2018

On Sets Defining Few Ordinary Circles

Frank de Zeeuw

An ordinary circle of a set P of n points in the plane is defined as a circle that contains exactly three points of P. We show that if P is not contained in a line or a circle, then P spans at least ordinary circles. Moreover, we determine the exact minimu ...

Springer2018

Photoinitiator-free Laser Fabrication of Ultra-compact, Low-loss Waveguides in Polydimethylsiloxane

Demetri Psaltis, Christophe Moser, Ye Pu, Giulia Panusa, Jieping Wang

Owing to its excellent elasticity, wide spectral range of transparency, and outstanding chemical and thermal stability, polydimethylsiloxane (PDMS) is an elastomer of great technological importance, being widely used in the fabrication of microfluidic and ...

SPIE-INT SOC OPTICAL ENGINEERING2018

Spread of proliferative kidney disease in fish along stream networks: A spatial metacommunity framework

Andrea Rinaldo, Enrico Bertuzzo, Lorenzo Mari, Luca Carraro, Marino Gatto

Proliferative kidney disease (PKD) is a high-mortality pathology that critically affects freshwater salmonid populations. Infection is caused by the endoparasitic myxozoan Tetracapsuloides bryosalmonae, which exploits freshwater bryozoans as primary hosts. ...

2018

Monochromatic cycle covers in random graphs

Dániel József Korándi

A classic result of Erdos, Gyarfas and Pyber states that for every coloring of the edges of K-n with r colors, there is a cover of its vertex set by at most f(r)=O(r2logr) vertex-disjoint monochromatic cycles. In particular, the minimum number of such cove ...

WILEY2018

Busy Man’s Synthesis: Combinational Delay Optimization With SAT

Giovanni De Micheli, Mathias Soeken

Boolean SAT solving can be used to find a minimum- size logic network for a given small Boolean function. This paper extends the SAT formulation to find a minimum-size network under delay constraints. Delay constraints are given in terms of input arrival t ...

Ieee2017

ESTIMA: Extrapolating ScalabiliTy of In-Memory Applications

Rachid Guerraoui, Aleksandar Dragojevic, Georgios Chatzopoulos

This article 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, ES ...

2017

Extension complexity of stable set polytopes of bipartite graphs

Yuri Faenza, Manuel Francesco Aprile

The extension complexity xc(P) of a polytope P is the minimum number of facets of a polytope that affinely projects to P. Let G be a bipartite graph with n vertices, m edges, and no isolated vertices. Let STAB(G) be the convex hull of the stable sets of G. ...

Springer2017