Publications related to Independent set (graph theory)

Geometric Graph Matching Using Monte Carlo Tree Search

Pascal Fua, Jan Kybic, Miguel Amável Dos Santos Pinheiro

We present an efficient matching method for generalized geometric graphs. Such graphs consist of vertices in space connected by curves and can represent many real world structures such as road networks in remote sensing, or vessel networks in medical imagi ...

Ieee Computer Soc2017

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

János Pach

In this paper, we prove several extremal results for geometrically defined hypergraphs. In particular, we establish an improved lower bound, single exponentially decreasing in k, on the best constant delta > 0 such that the vertex classes P-1,...,P-k of ev ...

Society for Industrial and Applied Mathematics2016

Independence number of generalized Petersen graphs

Javad Ebrahimi Boroojeni

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed towa ...

Charles Babbage Res Ctr2016

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

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

Removing and Adding Edges for the Traveling Salesman Problem

Ola Nils Anders Svensson

We present a framework for approximating the metric TSP based on a novel use of matchings. Traditionally, matchings have been used to add edges to make a given graph Eulerian, whereas our approach also allows for the removal of certain edges leading to a d ...

Assoc Computing Machinery2016

A 1D model of the arterial circulation in mice

Nikolaos Stergiopoulos, Lydia Aslanidou, Philippe Reymond, Bram Trachet, Patrick Segers

At a time of growing concern over the ethics of animal experimentation, mouse models are still an indispensable source of insight into the cardiovascular system and its most frequent pathologies. Nevertheless, reference data on the murine cardiovascular an ...

Spektrum Akademischer Verlag-Springer-Verlag Gmbh2016

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Ola Nils Anders Svensson, Lukas Polacek

The restricted max-min fair allocation problem (also known as the restricted Santa Claus problem) is one of few problems that enjoys the intriguing status of having a better estimation algorithm than approximation algorithm. Indeed, Asadpour et al. [2012] ...

Assoc Computing Machinery2016

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.

Independent set (graph theory)

Strengths and Limitations of Linear Programming Relaxations

Geometric Graph Matching Using Monte Carlo Tree Search

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Independence number of generalized Petersen graphs

On the Zarankiewicz problem for intersection hypergraphs

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

Removing and Adding Edges for the Traveling Salesman Problem

A 1D model of the arterial circulation in mice

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

Voltage stabilization in DC microgrids: an approach based on line-independent plug-and-play controllers

Graph Chatbot

Chat with Graph Search

Strengths and Limitations of Linear Programming Relaxations

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

Voltage stabilization in DC microgrids: an approach based on line-independent plug-and-play controllers

Geometric Graph Matching Using Monte Carlo Tree Search

On the Zarankiewicz problem for intersection hypergraphs

A Polynomial Regularity Lemma For Semialgebraic Hypergraphs And Its Applications In Geometry And Property Testing

Removing and Adding Edges for the Traveling Salesman Problem

Independence number of generalized Petersen graphs

Quasi-Polynomial Local Search for Restricted Max-Min Fair Allocation

A 1D model of the arterial circulation in mice