Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of CographsReportar como inadecuado




Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

* Corresponding author 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 2 LIGM - Laboratoire d-Informatique Gaspard-Monge

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





Autor: Christophe Crespelle - Philippe Gambette -

Fuente: https://hal.archives-ouvertes.fr/



DESCARGAR PDF




Documentos relacionados