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

Concept

Couplage (théorie des graphes)

Publications associées (31)

Atomic subgraphs and the statistical mechanics of networks

Sofia Charlotta Olhede

We develop random graph models where graphs are generated by connecting not only pairs of vertices by edges, but also larger subsets of vertices by copies of small atomic subgraphs of arbitrary topology. This allows for the generation of graphs with extens ...

2021

Space Efficient Approximation to Maximum Matching Size from Uniform Edge Samples

Slobodan Mitrovic, Mikhail Kapralov, Ashkan Norouzi Fard, Jakab Tardos

Given a source of iid samples of edges of an input graph G with n vertices and m edges, how many samples does one need to compute a constant factor approximation to the maximum matching size in G? Moreover, is it possible to obtain such an estimate in a sm ...

ASSOC COMPUTING MACHINERY2020

Minimum-Error Classes for Matching Parts

Thomas Alois Weber

This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...

2021

Dynamic Balanced Graph Partitioning

Andreas Loukas, Georg Stefan Schmid

This paper initiates the study of the classic balanced graph partitioning problem from an online perspective: Given an arbitrary sequence of pairwise communication requests between n nodes, with patterns that may change over time, the objective is to servi ...

SIAM Publications2020

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

Non-Exponential Variations for Classical Results in First Passage Percolation

Jacques Saliba

We study in this thesis the asymptotic behavior of optimal paths on a random graph model, the configuration model, for which we assign continuous random positive weights on its edges. We start by describing the asymptotic behavior of the diameter and the f ...

EPFL2020

On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus

Abhishek Methuku

Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8

2020

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

Several discrete geometry problems are equivalent to estimating the size of the largest homogeneous sets in graphs that happen to be the union of few comparability graphs. An important observation for such results is that if G is an n-vertex graph that is ...

CAMBRIDGE UNIV PRESS2020

Ramsey numbers of ordered graphs

Jan Kyncl

An ordered graph is a pair G = (G,

ELECTRONIC JOURNAL OF COMBINATORICS2020

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

Robust, High-Speed Interest Point Matching for Real-Time Applications

Michael Calonder

A typical Computer Vision system needs to process vast amounts of data as captured by one or more cameras, constantly testing the capabilities of today's hardware. Yet such systems face an ever-growing computational load caused by the more and more demandi ...

EPFL2010

Publications associées (31)

2020

Improved Ramsey-type results for comparability graphs

Istvan Tomon, Dániel József Korándi

CAMBRIDGE UNIV PRESS2020

Ramsey numbers of ordered graphs

Jan Kyncl

An ordered graph is a pair G = (G,

ELECTRONIC JOURNAL OF COMBINATORICS2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

2020

Robust, High-Speed Interest Point Matching for Real-Time Applications

Michael Calonder

EPFL2010