Concept

Maximal independent set

Related publications (108)

Local Approximation of the Maximum Cut in Regular Graphs

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

SPRINGER INTERNATIONAL PUBLISHING AG2019

On the Turan number of ordered forests

Gábor Tardos, Istvan Tomon, Dániel József Korándi

An ordered graph H is a simple graph with a linear order on its vertex set. The corresponding Turan problem, first studied by Pach and Tardos, asks for the maximum number ex(

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Stability results for vertex Turatn problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

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, Osman Emre Dai

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

Graph Laplacians for Rotation Equivariant Convolutional Neural Networks

Martino Milani

A fundamental problem in signal processing is to design computationally efficient algorithms to filter signals. In many applications, the signals to filter lie on a sphere. Meaningful examples of data of this kind are weather data on the Earth, or images o ...

2019

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

Gionata Ghiggi, Vincent Humphrey

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

A 4/3-Approximation Algorithm for the Minimum 2-Edge Connected Subgraph Problem

We present a factors 4/3 approximation algorithm for the problem of finding a minimum 2-edge connected spanning subgraph of a given undirected multigraph. The algorithm is based upon a reduction to a restricted class of graphs. In these graphs, the approxi ...

2019

A visual working memory dataset collection with bootstrap Independent Component Analysis for comparison of electroencephalographic preprocessing pipelines

Fiorenzo Artoni

Here we present an electroencephalographic (EEG) collection of 71-channel datasets recorded from 14 subjects (7 males, 7 females, aged 20–40 years) while performing a visual working memory task with a T set of 150 Independent Component Analysis (ICA) decom ...

2019

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.