Name
Abstract | ||
|---|---|---|
In this paper we show that the contiguity and linearity of cographs on n vertices are both O(logn). Moreover, we show that this bound is tight for contiguity as there exists a family of cographs on n vertices whose contiguity is @W(logn). We also provide an @W(logn/loglogn) lower bound on the maximum linearity of cographs on n vertices. 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 one of its path partitions. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.tcs.2013.11.036 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
path partition,tight bound,n vertex,maximum linearity,min-max theorem,minimum height | Journal | 522, |
ISSN | Citations | PageRank |
0304-3975 | 1 | 0.36 |
References | Authors | |
7 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christophe Crespelle | 1 | 62 | 11.02 |
| Philippe Gambette | 2 | 77 | 9.61 |