We introduce the problem of hub-laminar decomposition which generalizes that of computing a shortest path with minimum eccentricity (MESP). Intuitively, it consists in decomposing a graph into several paths that collectively have small eccentricity and meet only near their extremities. The problem is related to computing an isometric cycle with minimum eccentricity (MEIC). It is also linked to DNA reconstitution in the context of metagenomics in biology. We show that a graph having such a decomposition with long enough paths can be decomposed in polynomial time with approximated guaranties on the parameters of the decomposition. Moreover, such a decomposition with few paths allows to compute a compact representation of distances with additive distortion. We also show that having an isometric cycle with small eccentricity is related to the possibility of embedding the graph in a cycle with low distortion.

Given a family $\mathcal{F}$ of subsets of a ground set V, its orthogonal is defined to be the family of subsets that do not overlap any element of $\mathcal{F}$. Using this tool we revisit the problem of designing a simple linear time algorithm for undirected graph split (also known as 1-join) decomposition.

We study the measurement of the Internet according to two graph parameters: tree width and hyper bolicity. Both tell how far from a tree a graph is. They are computed from snapshots of the Internet released by CAIDA, DIMES, AQUALAB, UCLA, Rocket fuel and Strasbourg University, at the AS or at the router level. On the one hand, the tree width of the Internet appears to be quite large and being far from a tree with that respect, reflecting some high degree of connectivity. This proves the existence of a well linked core in the Internet. On the other hand, the hyper bolicity (as a graph parameter) appears to be very low, reflecting a tree-like structure with respect to distances. Additionally, we compute the tree width and hyper bolicity obtained for classical Internet models and compare with the snapshots.

In a distributed Video-on-Demand system, customers are in charge of storing the video catalog, and they actively participate in serving video requests generated by other customers. The design of such systems is driven by key constraints like customer upload and storage capacities, video popularity distribution, and so on. In this paper, we analyze by simulations the impact of: i) the video allocation technique (used for distributed storage) ii) the use of a cache that allows nodes to redistribute the video they are using iii) the use of static/dynamic algorithms for video distribution. Based on these results, we provide some guidelines for setting the system parameters: the use of cache strongly improves system performance; popularity based allocation techniques can be sensitive and bring little improvement; dynamic distribution algorithms are needed only in extreme scenarios while static ones are generally sufficient.

We consider the fully distributed video-on-demand problem, where n nodes called boxes store a large set of videos and collaborate to serve simultaneously n videos or less between them. It is said to be scalable when Omega (n) videos can be distributively stored under the condition that any sequence of demands for these videos can always be satisfied. Our main result consists in establishing a threshold on the average upload bandwidth of a box, above which the system becomes scalable. We are thus interested in the normalized upload capacity u = upload bandwidth/video bitrate of a box. The number m of distinct videos stored in the system is called its catalog size. We show an upload capacity threshold of 1 for scalability in a homogeneous system, where all boxes have the same upload capacity. More precisely, a system with u1, an homogeneous system where all boxes have same upload capacity at least u admits a static allocation of m = Omega (n) videos into the boxes such that any adversarial sequence of video demands can be satisfied. Moreover, such an allocation can be obtained randomly with high probability. This result is generalized to a system of boxes that have heterogeneous upload capacities under some balancing conditions.

We introduce a new approach to compute the common intervals of K permutations based on a very simple and general notion of generators of common intervals. This formalism leads to simple and efficient algorithms to compute the set of all common intervals of K permutations that can contain a quadratic number of intervals, as well as a linear space basis of this set of common intervals. Finally, we show how our results on permutations can be used for computing the modular decomposition of graphs.

This paper proposes a random Web crawl model. A Web crawl is a (biased and partial) image of the Web. This paper deals with the hyperlink structure, i.e. a Web crawl is a graph, whose vertices are the pages and whose edges are the hypertextual links. Of course a Web crawl has a very special structure; we recall some known results about it. We then propose a model generating similar structures. Our model simply simulates a crawling, i.e. builds and crawls the graph at the same time. The graphs generated have lot of known properties of Web crawls. Our model is simpler than most random Web graph models, but captures the sames properties. Notice that it models the crawling process instead of the page writing process of Web graph models.