Displaying similar documents to “A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation”

A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation

Marcia R. Cerioli, Luerbio Faria, Talita O. Ferreira, Fábio Protti (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

A is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a or . It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a -approximation algorithm for unit...

Comparing Imperfection Ratio and Imperfection Index for Graph Classes

Arie M.C.A. Koster, Annegret K. Wagler (2009)

RAIRO - Operations Research

Similarity:

Perfect graphs constitute a well-studied graph class with a rich structure, reflected by many characterizations with respect to different concepts. Perfect graphs are, for instance, precisely those graphs where the stable set polytope STAB() coincides with the fractional stable set polytope QSTAB(). For all imperfect graphs it holds that STAB() ⊂ QSTAB(). It is, therefore, natural to use the difference between the two polytopes in order to decide how far an imperfect graph...

Bootstrap clustering for graph partitioning

Philippe Gambette, Alain Guénoche (2011)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

Given a simple undirected weighted or unweighted graph, we try to cluster the vertex set into communities and also to quantify the robustness of these clusters. For that task, we propose a new method, called which consists in (i) defining a new clustering algorithm for graphs, (ii) building a set of graphs similar to the initial one, (iii) applying the clustering method to each of them, making a (set) of partitions, (iv) computing a consensus partition for this profile, which is the...

A note on the Size-Ramsey number of long subdivisions of graphs

Jair Donadelli, Penny E. Haxell, Yoshiharu Kohayakawa (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Let  be the graph obtained from a given graph  by subdividing each edge  times. Motivated by a problem raised by Igor Pak [Mixing time and long paths in graphs, in (SODA 2002) 321–328], we prove that, for any graph , there exist graphs  with  edges that are Ramsey with respect to  .

On the number of dissimilar pfaffian orientations of graphs

Marcelo H. de Carvalho, Cláudio L. Lucchesi, U. S.R. Murty (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

A subgraph of a graph is if has a perfect matching. An orientation of is if, for every conformal even circuit , the number of edges of whose directions in  agree with any prescribed sense of orientation of is odd. A graph is if it has a Pfaffian orientation. Not every graph is Pfaffian. However, if has a Pfaffian orientation , then the determinant of the adjacency matrix of is the square of the number of perfect matchings of . (See the book by Lovász and Plummer [. Annals...