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

Concept

Maximal independent set

Publications associées (28)

Anytime Heuristic for Weighted Matching Through Altruism-Inspired Behavior

Boi Faltings, Aris Filos Ratsikas, Panayiotis Danassis

We present a novel anytime heuristic (ALMA), inspired by the human principle of altruism, for solving the assignment problem. ALMA is decentralized, completely uncoupled, and requires no communication between the participants. We prove an upper bound on th ...

2019

Analysis of a Canonical Labeling Algorithm for the Alignment of Correlated Erdős-Rényi Graphs

Matthias Grossglauser, Negar Kiyavash

Graph alignment in two correlated random graphs refers to the task of identifying the correspondence between vertex sets of the graphs. Recent results have characterized the exact information-theoretic threshold for graph alignment in correlated Erdös-Rény ...

Association for Computing Machinery (ACM)2019

A note on discrete lattice-periodic sets with an application to Archimedean tilings

Matthias Schymura

Cao and Yuan obtained a Blichfeldt-type result for the vertex set of the edge-to-edge tiling of the plane by regular hexagons. Observing that the vertex set of every Archimedean tiling is the union of translates of a fixed lattice, we take a more general v ...

SPRINGER HEIDELBERG2019

Ordered Graphs And Large Bi-Cliques In Intersection Graphs Of Curves

János Pach, Istvan Tomon

An ordered graph G(

COMENIUS UNIV2019

Ordered graphs and large bi-cliques in intersection graphs of curves

János Pach, Istvan Tomon

An ordered graph G(

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

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

New Graph Algorithms via Polyhedral Techniques

Jakub Tarnawski

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

EPFL2019

GRUN: an observation-based global gridded runoff dataset from 1902 to 2014

Gionata Ghiggi

Freshwater resources are of high societal relevance, and understanding their past variability is vital to water management in the context of ongoing climate change. This study introduces a global gridded monthly reconstruction of runoff covering the period ...

Copernicus GmbH2019