Concept
Union-find
Publications associées (40)
Sketches, metrics and fast algorithms
As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...
EPFL2022Promoting Connectivity of Network-Like Structures by Enforcing Region Separation
Pascal Fua, Doruk Oner, Mateusz Kozinski, Leonardo Citraro
We propose a novel, connectivity-oriented loss function for training deep convolutional networks to reconstruct network-like structures, like roads and irrigation canals, from aerial images. The main idea behind our loss is to express the connectivity of r ...
2021Large-Scale Crowdsourcing Subjective Quality Evaluation of Learning-Based Image Coding
Touradj Ebrahimi, Evgeniy Upenik, Michela Testolina
Learning-based image codecs produce different compression artifacts, when compared to the blocking and blurring degradation introduced by conventional image codecs, such as JPEG, JPEG~2000 and HEIC. In this paper, a crowdsourcing based subjective quality e ...
IEEE2021Symbolic 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 ...
2020Fully dynamic bin packing revisited
Kim-Manuel Klein, Klaus Jansen
We consider the fully dynamic bin packing problem, where items arrive and depart in an online fashion and repacking of previously packed items is allowed. The goal is, of course, to minimize both the number of bins used as well as the amount of repacking. ...
SPRINGER HEIDELBERG2020Monopulse Beam Synthesis Using a Sparse Single Layer of Weights
A conventional monopulse radar system uses three beams, namely, sum beam, elevation difference beam, and azimuth difference beam, which require different layers of weights to synthesize each beam independently. Since the multilayer structure increases the ...
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2019Approximating the rectilinear crossing number
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 ...
2019Finding Perfect Matchings in Bipartite Hypergraphs
Haxell's condition [14] is a natural hypergraph analog of Hall's condition, which is a well-known necessary and sufficient condition for a bipartite graph to admit a perfect matching. That is, when Haxell's condition holds it forces the existence of a perf ...
SPRINGER HEIDELBERG2018Many disjoint edges in topological graphs
A monotone cylindrical graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called simple if any pair of its edges have at most one ...
Elsevier Science Bv2017Families with no s pairwise disjoint sets
For integers n >= s >= 2 let e (n, s) denote the maximum of vertical bar F vertical bar, where F is a family of subsets of an n- element set and F contains no s pairwise disjoint members. Half a century ago, solving a conjecture of Erd. os, Kleitman determ ...
Wiley2017