Block decomposition approach to compute a minimum geodetic set

Tınaz Ekim; Aysel Erey

Displaying similar documents to “Block decomposition approach to compute a minimum geodetic set”

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

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...

Minimum convex-cost tension problems on series-parallel graphs

Bruno Bachelet, Philippe Mahey (2010)

RAIRO - Operations Research

Similarity:

We present briefly some results we obtained with known methods to solve minimum cost tension problems, comparing their performance on non-specific graphs and on series-parallel graphs. These graphs are shown to be of interest to approximate many tension problems, like synchronization in hypermedia documents. We propose a new method to solve the minimum convex piecewise linear cost tension problem on series-parallel graphs in operations.