Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Concept

Disjoint-set data structure

Related publications (14)

Sketches, metrics and fast algorithms

Navid Nouri

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 ...

EPFL2022

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

Monopulse Beam Synthesis Using a Sparse Single Layer of Weights

Semin Kwak

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 INC2019

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

Finding Perfect Matchings in Bipartite Hypergraphs

Chidambaram Annamalai

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-Verlag2018

Many disjoint edges in topological graphs

Andres Jacinto Ruiz Vargas

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 Bv2017

Families with no s pairwise disjoint sets

Andrei Kupavskii

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

A size-sensitive inequality for cross-intersecting families

Andrei Kupavskii

Two families A and B, of k-subsets of an n-set are called cross intersecting if A boolean AND B not equal phi for all A,B epsilon b. Strengthening the classical ErclOs-Ko-Rado theorem, Pyber proved that vertical bar A vertical bar vertical bar B vertical b ...

Academic Press Ltd- Elsevier Science Ltd2017

Ballistocardiogram artifact correction taking into account physiological signal preservation in simultaneous EEG-fMRI

Wietske Van der Zwaag, João Pedro Forjaco Jorge, Patricia Figueiredo, Ana Francisca Leal Silva Soares

The ballistocardiogram (BCG) artifact is currently one of the most challenging in the EEG acquired concurrently with fMRI, with correction invariably yielding residual artifacts and/or deterioration of the physiological signals of interest. In this paper, ...

Elsevier2016

On the Zarankiewicz problem for intersection hypergraphs

János Pach

Let d and t be fixed positive integers, and let denote the complete d-partite hypergraph with t vertices in each of its parts, whose hyperedges are the d-tuples of the vertex set with precisely one element from each part. According to a fundamental theorem ...

Academic Press Inc Elsevier Science2016

Simple topological graphs : empty triangles and disjoint edges

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any t ...

EPFL2016

Decision Procedures for Program Synthesis and Verification

Ruzica Piskac

Decision procedures are widely used in software development and verification. The goal of this dissertation is to increase the scope of properties that can be verified using decision procedures. To achieve this goal, we identify three improvements over the ...

EPFL2011

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Related publications (14)