Concept

Independent set (graph theory)

Related publications (164)

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.

String graphs and incomparability graphs

János Pach

Given a collection C of curves in the plane, its string graph is defined as the graph with vertex set C, in which two curves in C are adjacent if and only if they intersect. Given a partially ordered set (P,

2012

k-Quasi-Planar Graphs

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi. and Szegedy [16 ...

Springer-Verlag Berlin2012

Practical Network Tomography

Denisa Gabriela Ghita

In this thesis, we investigate methods for the practical and accurate localization of Internet performance problems. The methods we propose belong to the field of network loss tomography, that is, they infer the loss characteristics of links from end-to-en ...

EPFL2012

A note on chromatic properties of threshold graphs

Dominique de Werra, Bernard Ries, Rico Zenklusen

In threshold graphs one may find weights for the vertices and a threshold value t such that for any subset S of vertices, the sum of the weights is at most the threshold t if and only if the set S is a stable (independent) set. In this note we ask a simila ...

2012

Heisenberg uncertainty principle as a probe of entanglement entropy: Application to superradiant quantum phase transitions

Pierre Marcel Nataf

Quantum phase transitions are often embodied by the critical behavior of purely quantum quantities such as entanglement or quantum fluctuations. In critical regions, we underline a general scaling relation between the entanglement entropy and one of the mo ...

Amer Physical Soc2012

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. [1] pro ...

Springer2012

Coloring fuzzy circular interval graphs

Friedrich Eisenbrand, Martin Niemeier

Given a graph G with nonnegative node labels w, a multiset of stable sets S_1,...,S_k\subseteq V(G) such that each vertex v \in V(G) is contained in w(v) many of these stable sets is called a weighted coloring. The weighted coloring number \chi_w(G) is the ...

Elsevier2012

Network community-detection enhancement by proper weighting

Martin Hasler, Ali Ajdari Rad, Alireza Khadivi

In this article, we show how proper assignment of weights to the edges of a complex network can enhance the detection of communities and how it can circumvent the resolution limit and the extreme degeneracy problems associated with modularity. Our general ...

American Physical Society2011

A Regularization Framework for Mobile Social Network Analysis

Pascal Frossard, Pierre Vandergheynst, Xiaowen Dong

Mobile phone data provides rich dynamic information on human activities in social network analysis. In this paper, we represent data from two different modalities as a graph and functions defined on the vertex set of the graph. We propose a regularization ...

2011

An algorithmic decomposition of claw-free graphs leading to an O(n^3) algorithm for the weighted stable set problem

Yuri Faenza, Gautier Stauffer

We propose an algorithm for solving the maximum weighted stable set problem on claw-free graphs that runs in O(n^3)-time, drastically improving the previous best known complexity bound. This algorithm is based on a novel decomposition theorem for claw-free ...

2011