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

Christophe Crespelle 1, * Philippe Gambette 2
* 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
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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-00755257
Contributor : Christophe Crespelle <>
Submitted on : Friday, November 23, 2012 - 11:01:16 AM
Last modification on : Thursday, February 7, 2019 - 2:34:51 PM
Long-term archiving on : Sunday, February 24, 2013 - 3:46:58 AM

File

CographContiguity.pdf
Files produced by the author(s)

Identifiers

Citation

Christophe Crespelle, Philippe Gambette. Linear-time Constant-ratio Approximation Algorithm and Tight Bounds for the Contiguity of Cographs. Seventh International Workshop on Algorithms and Computation, Feb 2013, Kharagpur, India. pp.126-136, ⟨10.1007/978-3-642-36065-7_13⟩. ⟨hal-00755257⟩

Share

Metrics

Record views

711

Files downloads

254