Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs

Christophe Crespelle 1, * Philippe Gambette 2
* Auteur correspondant
1 DANTE - Dynamic Networks : Temporal and Structural Capture Approach
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme, IXXI - Institut Rhône-Alpin des systèmes complexes
Abstract : In this paper we consider a graph parameter called contiguity which aims at encoding a graph by a linear ordering of its vertices. We prove that the contiguity of cographs is unbounded but is always dominated by O(log n), where n is the number of vertices of the graph. And we prove that this bound is tight in the sense that there exists a family of cographs on n vertices whose contiguity is Omega(log n). In addition to these results on the worst-case contiguity of cographs, we design a linear-time constant-ratio approximation algorithm for computing the contiguity of an arbitrary cograph, which constitutes our main result. As a by-product of our proofs, we obtain a min-max theorem, which is worth of interest in itself, stating equality between the rank of a tree and the minimum height of its path partitions.
Type de document :
Communication dans un congrès
Ghosh, Subir Kumar and Tokuyama, Takeshi. Seventh International Workshop on Algorithms and Computation, Feb 2013, Kharagpur, India. Springer, 7748, pp.126-136, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-36065-7_13〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00755257
Contributeur : Christophe Crespelle <>
Soumis le : vendredi 23 novembre 2012 - 11:01:16
Dernière modification le : jeudi 12 juillet 2018 - 01:05:09
Document(s) archivé(s) le : dimanche 24 février 2013 - 03:46:58

Fichier

CographContiguity.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Christophe Crespelle, Philippe Gambette. Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs. Ghosh, Subir Kumar and Tokuyama, Takeshi. Seventh International Workshop on Algorithms and Computation, Feb 2013, Kharagpur, India. Springer, 7748, pp.126-136, 2013, Lecture Notes in Computer Science. 〈10.1007/978-3-642-36065-7_13〉. 〈hal-00755257〉

Partager

Métriques

Consultations de la notice

625

Téléchargements de fichiers

169