In the standard Freeze-Tag Problem (FTP), an initially awake robot (the source) is in charge of waking up a swarm of sleeping robots by moving towards them, given that all the awake robots can participate in the awakening process. The goal is to minimize the makespan to wake up all robots assuming they move at unit speed. In this paper we introduce the Freeze-Tag-with-Return Problem (FTRP) variant, where the robots must eventually return to their initial positions. In the Euclidean plane with n sleeping robots lying on the unit disk centered at the initial position of the source, we show a non-trivial relationship between FTP and FTRP by proving that the difference between the optimal makespan of both problems never exceeds 1.959, and is at least 1.732 in the worst-case. We also present several upper and lower bounds on the optimal makespan. In particular, we show that if the sleeping robots are in convex positions, then the optimal makespan is at most 2 + 2√2, which is achieved by some instances. From an algorithmic point-of-view, we present single-exponential algorithms for general distance functions. In metric spaces, these algorithms are asymptotically optimal under the ETH, which we show via an NP-hardness reduction on unweighted graphs.

We prove that given any α-approximation LOCAL algorithm for Minimum Dominating Set (MDS) on planar graphs, we can construct an f(g)-round (3α + 1)-approximation LOCAL algorithm for MDS on graphs embeddable in a given Euler genus-g surface. Heydt et al. [European Journal of Combinatorics (2025)] gave an algorithm with α = 11 + ϵ, from which we derive a (34 + ϵ)-approximation algorithm for graphs of genus g, therefore improving upon the current state of the art of 24g + O(1) due to Amiri et al. [ACM Transactions on Algorithms (2019)]. It also improves the approximation ratio of 91 + ϵ due to Czygrinow et al. [Theoretical Computer Science (2019)] in the particular case of orientable surfaces.

A covering path for a finite set P of points in the plane is a polygonal path such that every point of P lies on a segment of the path. The vertices of the path need not be at points of P. A covering path is plane if its segments do not cross each other. Let π(n) be the minimum number such that every set of n points in the plane admits a plane covering path with at most π(n) segments. We prove that π(n) ≤ ⌈6n/7⌉. This improves the previous best-known upper bound of ⌈21n/22⌉, due to Biniaz (SoCG 2023). Our proof is constructive and yields a simple O(n log n)-time algorithm for computing a plane covering path.

We give a series of new lower bounds on the minimum number of vertices required by a graph to contain every graph of a given family as induced subgraph. In particular, we show that this induced-universal graph for n -vertex planar graphs must have at least 10.52 n vertices. We also show that the number of conflicting graphs to consider in order to beat this lower bound is at least 137. In other words, any family of less than 137 planar graphs of n vertices has an induced-universal graph with less than 10.52 n vertices, stressing the difficulty in beating such lower bounds. Similar results are developed for other graph families, including but not limited to, trees, outerplanar graphs, series-parallel graphs, K 3,3 -minor free graphs. As a byproduct, we show that any family of t graphs of n vertices having small chromatic number and sublinear pathwidth, like any proper minor-closed family, has an induced-universal graph with less than 15/7 √t⋅n vertices. If t ⩾ n 2 , the bound actually holds for any family of t graphs. Our results are achieved by making a bridge between equitable colorings, combinatorial designs, and path-decompositions.

A query algorithm based on homomorphism counts is a procedure to decide membership for a class of finite relational structures using only homomorphism count queries. A left query algorithm can ask the number of homomorphisms from any structure to the input structure and a right query algorithm can ask the number of homomorphisms from the input structure to any other structure. We systematically compare the expressive power of different types of left or right query algorithms, including non-adaptive query algorithms, adaptive query algorithms that can ask a bounded number of queries, and adaptive query algorithms that can ask an unbounded number of queries. We also consider query algorithms where the homomorphism counting is done over the Boolean semiring $\mathbb{B}$, meaning that only the existence of a homomorphism is recorded, not the precise number of them.

We show that graphs excluding K2,t as a minor admit a f(t)-round 50-approximation deterministic distributed algorithm for Minimum Dominating Set. The result extends to Minimum Vertex Cover. Though fast and approximate distributed algorithms for such problems were already known for H-minor-free graphs, all of them have an approximation ratio depending on the size of H. To the best of our knowledge, this is the first example of a large non-trivial excluded minor leading to fast and constant-approximation distributed algorithms, where the ratio is independent of the size of H. A new key ingredient in the analysis of these distributed algorithms is the use of asymptotic dimension.

The Freeze-Tag Problem consists in waking up a swarm of robots starting with one initially awake robot. While there exists a wide literature on the centralized setting, where the locations of the robots are known in advance, we focus on the distributed version where the locations of the robots, P, are unknown, and where awake robots only detect other robots up to distance 1. Assuming that moving at distance δ takes a time δ, we show that waking up the whole swarm takes O(ρ + ℓ2 log(ρ/ℓ)), where ρ is the largest distance from the initial robot to any point of P, and ℓ is the connectivity threshold of P. Moreover, the result is complemented by a matching lower bound. We also provide other distributed algorithms, complemented with lower bounds, whenever each robot has a bounded amount of energy.

The Freeze-Tag Problem, introduced in Arkin et al. (SODA'02) consists of waking up a swarm of n robots, starting from a single active robot. In the basic geometric version, every robot is given coordinates in the plane. As soon as a robot is awakened, it can move towards inactive robots to wake them up. The goal is to minimize the makespan of the last robot, the makespan. Despite significant progress on the computational complexity of this problem and on approximation algorithms, the characterization of exact bounds on the makespan remains one of the main open questions. In this paper, we settle this question for the 𝓁₁-norm, showing that a makespan of at most 5r can always be achieved, where r is the maximum distance between the initial active robot and any sleeping robot. Moreover, a schedule achieving a makespan of at most 5r can be computed in time O(n). Both bounds, the time and the makespan are optimal. Our results also imply for the 𝓁₂-norm a new upper bound of 5√2r ≈ 7.07r on the makespan, improving the best known bound of (5+2√2+√5)r ≈ 10.06r. Along the way, we introduce new linear time wake-up strategies, that apply to any norm and show that an optimal bound on the makespan can always be achieved by a schedule computable in linear time.

No abstract available.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n -vertex planar graph G is assigned a (1 + o(1)) log 2 n -bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G . This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n , there exists a graph U n with n 1+o(1) vertices such that every n -vertex planar graph is an induced subgraph of U n . These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k -planar graphs.

A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$ coincide with the distances between the corresponding vertices in $G$. We show that for any integer $n\ge 1$, there is a graph on $3^{n+O(\log^2 n)}$ vertices that contains isometric copies of all $n$-vertex graphs. Our main tool is a new type of distance labelling scheme, whose study might be of independent interest.

We show that there exists an adjacency labelling scheme for planar graphs where each vertex of an n-vertex planar graph G is assigned a (1+o(1))log2n-bit label and the labels of two vertices u and v are sufficient to determine if uv is an edge of G. This is optimal up to the lower order term and is the first such asymptotically optimal result. An alternative, but equivalent, interpretation of this result is that, for every positive integer n, there exists a graph Un with n1+o(1)vertices such that every n-vertex planar graph is an induced subgraph of Un. These results generalize to a number of other graph classes, including bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

An adjacency labeling scheme for a given class of graphs is an algorithm that, for every graph $G$ from the class, assigns bit strings (labels) to vertices of $G$ so that for any two vertices $u,v$, whether $u$ and $v$ are adjacent can be determined by a fixed procedure that examines only their labels. It is known that planar graphs with $n$ vertices admit a labeling scheme with labels of bit length $(2+o(1))\log{n}$. In this work we improve this bound by designing a labeling scheme with labels of bit length $(\frac{4}{3}+o(1))\log{n}$. All the labels of the input graph can be computed in polynomial time, while adjacency can be decided from the labels in constant time. In graph-theoretical terms, this implies an explicit construction of a graph on $n^{4/3+o(1)}$ vertices that contains all planar graphs on $n$ vertices as induced subgraphs, improving the previous best upper bound of $n^{2+o(1)}$. Our labeling scheme can be generalized to larger classes of topologically constrained graphs, for instance, to graphs embeddable in any fixed surface or to $k$-planar graphs for any fixed $k$, at the cost of larger second-order terms.

We prove that any graph excluding $K_r$ as a minor can be partitioned into clusters of diameter at most $\Delta$ while removing at most $O(r/\Delta)$ fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who, building on the work of Klein, Plotkin, and Rao, gave a partitioning that required removing $O(r^2/\Delta)$ fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter $O(r)$ and strong-diameter partitions with padding parameter $O(r^2)$ for $K_r$-minor-free graphs, $O(k)$ for treewidth-$k$ graphs, and $O(\log g)$ for graphs with (Euler) genus $g$.

Let S be a finite set of points in the plane that are in convex position. We present an algorithm that constructs a plane frac{3+4 pi}{3}-spanner of S whose vertex degree is at most 3. Let Lambda be the vertex set of a finite non-uniform rectangular lattice in the plane. We present an algorithm that constructs a plane 3 sqrt{2}-spanner for Lambda whose vertex degree is at most 3. For points that are in the plane and in general position, we show how to compute plane degree-3 spanners with a linear number of Steiner points.

We consider how to assign labels to any undirected graph with n nodes such that, given the labels of two nodes and no other information regarding the graph, it is possible to determine the distance between the two nodes. The challenge in such a distance labeling scheme is primarily to minimize the maximum label length and secondarily to minimize the time needed to answer distance queries (decoding). Previous schemes have offered different tradeoffs between label lengths and query time. This paper presents a simple algorithm with shorter labels and shorter query time than any previous solution, thereby improving the state-of-the-art with respect to both label length and query time in one single algorithm. Our solution addresses several open problems concerning label length and decoding time and is the first improvement of label length for more than three decades. More specifically, we present a distance labeling scheme with labels of length bits1 and constant decoding time. This outperforms all existing results with respect to both size and decoding time, including Winkler's (Combinatorica 1983) decade-old result, which uses labels of size (log 3)n and O(n/log n) decoding time, and Gavoille et al. (SODA'01), which uses labels of size 11n + o(n) and O(log log n) decoding time. In addition, our algorithm is simpler than the previous ones. In the case of integral edge weights of size at most W, we present almost matching upper and lower bounds for the label size . Furthermore, for r-additive approximation labeling schemes, where distances can be off by up to an additive constant r, we present both upper and lower bounds. In particular, we present an upper bound for 1-additive approximation schemes which, in the unweighted case, has the same size (ignoring second order terms) as an adjacency labeling scheme, namely n/2. We also give results for bipartite graphs as well as for exact and 1-additive distance oracles.

This article proposes a forbidden-set labeling scheme for the family of unweighted graphs with doubling dimension bounded by α. For an n -vertex graph G in this family, and for any desired precision parameter ϵ > 0, the labeling scheme stores an O (1 + ϵ − 1 ) 2α log 2 n -bit label at each vertex. Given the labels of two end-vertices s and t , and the labels of a set F of “forbidden” vertices and/or edges, our scheme can compute, in O (1 + ϵ − 1 ) 2α · | F | 2 log n time, a 1 + ϵ stretch approximation for the distance between s and t in the graph G ∖ F . The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ϵ for graphs of bounded doubling dimension.

This paper investigates compact routing schemes that are very efficient with respect to the memory used to store routing tables in internet-like graphs. We propose a new compact name-independent routing scheme whose theoretically proven average memory per node is upper-bounded by nγ, with constant γ < 1/2, while the maximum memory of any node is bounded by √n and the maximum stretch of any route is bounded by 5. These bounds are given for the Random Power Low Graphs (RPLG) and hold with high probability. Moreover, we experimentally show that our scheme is very efficient in terms of stretch and memory in internet-like graphs (CAIDA and other maps). We complete this study by comparing our analytic and experimental results to several compact routing schemes. In particular, we show that the average memory requirements is better by at least one order of magnitude than previous schemes for CAIDA maps on 16K nodes.

We prove that any graph excluding Kr as a minor has can be partitioned into clusters of diameter at most Δ while removing at most O(r/Δ) fraction of the edges. This improves over the results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning that required to remove O(r2/Δ) fraction of the edges. Our result is obtained by a new approach that relates the topological properties (excluding a minor) of a graph to its geometric properties (the induced shortest path metric). Specifically, we show that techniques used by Andreae in his investigation of the cops and robbers game on graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter O(r) and strong-diameter partitions with padding parameter O(r2) for Kr-free graphs, O(k) for treewidth-k graphs, and O(log g) for graphs with genus g.

This paper considers fully dynamic (1+ε) distance oracles and (1+ε) forbidden-set labeling schemes for planar graphs. For a given n-vertex planar graph G with edge weights drawn from [1,M] and parameter ε>0, our forbidden-set labeling scheme uses labels of length λ = O(ε-1 log2n log(nM) • maxlogn). Given the labels of two vertices s and t and of a set F of faulty vertices/edges, our scheme approximates the distance between s and t in G \ F with stretch (1+ε), in O(|F|2 λ) time.

Routing with multiplicative stretch 3 (which means that the path used by the routing scheme can be up to three times longer than a shortest path) can be done with routing tables of Θ(√n) bits per node. The space lower bound is due to the existence of dense graphs with large girth. Dense graphs can be sparsified to subgraphs, called spanners, with various stretch guarantees. There are spanners with additive stretch guarantees (some even have constant additive stretch) but only very few additive routing schemes are known.

The paper proposes a forbidden-set labeling scheme for the family of graphs with doubling dimension bounded by α. For an n-vertex graph G in this family, and for any desired precision parameter ε > 0, the labeling scheme stores an O(1+α-1)2α log2 n-bit label at each vertex. Given the labels of two end-vertices s and t, and the labels of a set F of "forbidden" vertices and/or edges, our scheme can compute, in time polynomial in the length of the labels, a 1+ε stretch approximation for the distance between s and t in the graph GF. The labeling scheme can be extended into a forbidden-set labeled routing scheme with stretch 1 + ε for graphs of bounded doubling dimension.

Abstract Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)‐Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

The paper presents a deterministic distributed algorithm that, given k ≥ 1, constructs in k rounds a (2k-1,0)-spanner of O(k n1+1/k) edges for every n-node unweighted graph. (If n is not available to the nodes, then our algorithm executes in 3k-2 rounds, and still returns a (2k-1,0)-spanner with O(k n1+1/k) edges.) Previous distributed solutions achieving such optimal stretch-size trade-off either make use of randomization providing performance guarantees in expectation only, or perform in logΩ(1)n rounds, and all require a priori knowledge of n. Based on this algorithm, we propose a second deterministic distributed algorithm that, for every ε > 0, constructs a (1+ε,2)-spanner of O(ε-1 n3/2) edges in O(ε-1) rounds, without any prior knowledge on the graph.

Graph augmentation theory is a general framework for analyzing navigability in social networks. It is known that, for large classes of graphs, there exist augmentations of these graphs such that greedy routing according to the shortest path metric performs in polylogarithmic expected number of steps. However, it is also known that there are classes of graphs for which no augmentations can enable greedy routing according to the shortest path metric to perform better than Ω(n1/√log n) expected number of steps. In fact, the best known universal bound on the greedy diameter of arbitrary graph is essentially n1/3. That is, for any graph, there is an augmentation such that greedy routing according to the shortest path metric performs in Õ(n1/3) expected number of steps. Hence, greedy routing according to the shortest path metric has at least two drawbacks. First, it is in general space-consuming to encode locally the shortest path distances to all the other nodes, and, second, greedy routing according to the shortest path metric performs poorly in some graphs.

A distance labeling scheme is a distributed graph representation that assigns labels to the vertices and enables answering distance queries between any pair $(x,y)$ of vertices by using only the labels of x and y. This paper presents an optimal distance labeling scheme with labels of $\mathcal{O}(\log n)$ bits for the n-vertex interval graphs family. It improves by $\log n$ factor the best known upper bound of [M. Katz, N. A. Katz, and D. Peleg, Distance labeling schemes for well-separated graph classes, in Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. 1770, Springer-Verlag, Berlin, 2000, pp. 516–528]. Moreover, the scheme supports constant time distance queries, and if the interval representation of the input graph is given and the intervals are sorted, then the set of labels can be computed in $\mathcal{O}(n)$ time. Our result is tight as we show that the length of any label is at least $3\log n-\mathcal{O}(\log\log n)$ bits. This lower bound derives from a new estimator of the number of unlabeled n-vertex interval graphs, that is, $2^{\Omega(n \log n)}$. To our knowledge, interval graphs are thereby the first known nontrivial hereditary family with $2^{\Omega(n f(n))}$ unlabeled elements and with a distance labeling scheme with $f(n)$ bit labels.

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a Õ (√n,) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the minimum cost paths. This is optimal in a very strong sense. It is known that no compact routing using o ( n ) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√ n ,)space per node.

We consider distributed representation scheme for trees, supporting some special relationships between nodes at small distance. For instance, we show that for a tree T and an integer k we can assign local information on nodes such that we can decide for two nodes u and v if the distance between u and v is at most k and if so, compute it only using the local information assigned. For trees withn nodes, the local information assigned by our scheme is binary label of log n + O(klog(klog(n/k))) bits, improving a recent result of Alstrup, Bille and Rauhe.

We provide the first sparse covers and probabilistic partitions for graphs excluding a fixed minor that have strong diameter bounds; i.e. each set of the cover/partition has a small diameter as an induced sub-graph. Using these results we provide improved distributed name-independent routing schemes. Specifically, given a graph excluding a minor on r vertices and a parameter ρ > 0 we obtain the flowing results: (1) a polynomial algorithm that constructs a set of clusters such that each cluster has a strong-diameter of O(r2ρ) and each vertex belongs to 2O(r)r! clusters; (2) a name-independent routing scheme with a stretch of O(r2) and tables of size 2O(r)r! log4n bits; (3) a randomized algorithm that partitions the graph such that each cluster has strong-diameter O(r6r ρ) and the probability an edge (u, v) is cut is O(r d(u, v)/ρ).

Augmented graphs were introduced for the purpose of analyzing the "six degrees of separation between individuals" observed experimentally by the sociologist Standley Milgram in the 60's. Formally, an augmented graph is a pair (G,φ) where G is a graph, and φ is a collection of probability distributions {φu, u ∈ V(G)}. Every node u ∈ V(G) is given an extra link, called a long range link, pointing to some node v, called the long range contact of u. The head v of this link is chosen at random by Pr{u → v} = φu(v). In augmented graphs, greedy routing is the oblivious routing process in which every intermediate node chooses among all its neighbors (including its long range contact) the one that is closest to the target according to the distance measured in the underlying graph G, and forwards to it. Roughly, augmented graphs aim at modeling the structure of social networks, while greedy routing aims at modeling the searching procedure applied in Milgram's experiment. Our objective is to design efficient universal augmentation schemes, i.e., augmentation schemes that give to any graph G a collection of probability distributions φ such that greedy routing in (G,φ) is fast. It is known that the uniform scheme φunif is a universal scheme ensuring that, for any n-node graph G, greedy routing in (G,φunif) performs in O(√n) expected number of steps. Our main result is the design of a universal augmentation scheme φ such that greedy routing in (G,φ) performs in Õ(n1/3) expected number of steps for any n-node graph G. We also show that under some more restricted model, the √n-barrier cannot be overcome.

This paper studies compact routing schemes for networks with low doubling dimension. Two variants are explored, name-independent routing and labeled routing. The key results obtained for this model are the following. First, we provide the first name-independent solution. Specifically, we achieve constant stretch and polylogarithmic storage. Second, we obtain the first truly scale-free solutions, namely, the network’s aspect ratio is not a factor in the stretch. Scale-free schemes are given for three problem models: name-independent routing on graphs, labeled routing on metric spaces, and labeled routing on graphs. Third, we prove a lower bound requiring linear storage for stretch \gt 3 schemes. This has the important ramification of separating for the first time the name-independent problem model from the labeled model for these networks, since compact stretch-1+e labeled schemes are known to be possible.

We study a novel separator property called k-path separable. Roughly speaking, a k-path separable graph can be recursively separated into smaller components by sequentially removing k shortest paths. Our main result is that every minor free weighted graph is k-path separable. We then show that k-path separable graphs can be used to solve several object location problems: (1) a small-worldization with an average poly-logarithmic number of hops; (2) an (1 + ε)-approximate distance labeling scheme with O(log n) space labels; (3) a stretch-(1 + ε) compact routing scheme with tables of poly-logarithmic space; (4) an (1 + ε)-approximate distance oracle with O(n log n) space and O(log n) query time. Our results generalizes to much wider classes of weighted graphs, namely to bounded-dimension isometric sparable graphs.

One of the fundamental trade-offs in compact routing schemes is between the space used to store the routing table on each node and the stretch factor of the routing scheme -- the ratio between the cost of the route induced by the scheme and the cost of a minimum cost path between the same pair. Using a distributed Kolmogorov Complexity argument, we give a lower bound for the name-independent model that applies even to single-source schemes and does not require a girth conjecture. For any integer k ≥ 1 we prove that any routing scheme for networks with arbitrary weights and arbitrary node names (even a single-source routing scheme) with maximum stretch strictly less than 2k + 1 requires Ω((n log n)1/k)-bit routing tables. We extend our results to lower bound the average-stretch, showing that for any integer k ≥ 1 any name-independent routing scheme with (n/(9k))1/k-bit routing tables has average-stretch of at least k/4 + 7/8. This result is in sharp contrast to recent results on the average-stretch of labeled routing schemes.

International audience

We consider small world graphs as defined by Kleinberg (2000), i.e., graphs obtained from a d-dimensional mesh by adding links chosen at random according to the d-harmonic distribution. This model aims at giving formal support to the "six degrees of separation" between individuals experienced by Milgram (1967),and verified recently by Dodds, Muhamad, and Watts (2003). In particular, Kleinberg shows that greedy routing performs in O(log2n) expected number of steps in d-dimensional augmented meshes, with O(log2n) bits of topological awareness per node, for any constant d ≥ 1. We show that giving O(log2n) bits of topological awareness per node decreases the expected number of steps of greedy routing to O(log1+1/dn) in d-dimensional augmented meshes. We also show that, independently of the amount of topological awareness given to the nodes, greedy routing performs in Ω(log1+1/dn) expected number of steps. In particular, augmenting the topological awareness above this optimum of O(log2n) bits would drastically decrease the performances of greedy routing. Moreover, our model demonstrates that the efficiency of greedy routing is sensible to the "world's dimension", in the sense that high dimensional worlds enjoy faster greedy routing than low dimensional ones. This could not be observed in Kleinberg's model. In addition to bringing new light to Milgram's experiment, our protocol presents several desirable properties. In particular, it is totally oblivious i.e., there is no header modification along the path from the source to the target, and the routing decision depends only on the target, and on information stored locally at each node. Finally, our protocol can obviously be used for the design of DHTs, in the same spirit as Symphony (2003).

Given a weighted undirected network with arbitrary node names, we present a compact routing scheme, using a O(√n) space routing table at each node, and routing along paths of stretch 3, that is, at most thrice as long as the shortest paths. This is optimal in a very strong sense. It is known that no compact routing using o(n) space per node can route with stretch below 3. Also, it is known that any stretch below 5 requires Ω(√n) space per node.

Several papers describe linear time algorithms to preprocess a tree, such that one can answer subsequent nearest common ancestor queries in constant time. Here, we survey these algorithms and related results. A common idea used by all the algorithms for the problem is that a solution for complete binary trees is straightforward. Furthermore, for complete binary trees we can easily solve the problem in a distributed way by labeling the nodes of the tree such that from the labels of two nodes alone one can compute the label of their nearest common ancestor. Whether it is possible to distribute the data structure into short labels associated with the nodes is important for several applications such as routing. Therefore, related labeling problems have received a lot of attention recently.Previous optimal algorithms for nearest common ancestor queries work using some mapping from a general tree to a complete binary tree. However, it is not clear how to distribute the data structures obtained using these mappings. We conclude our survey with a new simple algorithm that labels the nodes of a rooted tree such that from the labels of two nodes alone one can compute in constant time the label of their nearest common ancestor. The labels assigned by our algorithm are of size $O(\log n)$ bits where $n$ is the number of nodes in the tree. The algorithm runs in $O(n)$ time.

Interval routing is a compact way of representing routing tables on a graph. It is based on grouping together, in each node, destination addresses that use the same outgoing edge in the routing table. Such groups of addresses are represented by some intervals of consecutive integers. We show that almost all the graphs, i.e., a fraction of at least 1-1/n 2 of all the n-node graphs, support a shortest path interval routing with three intervals per outgoing edge, even if the addresses of the nodes are arbitrarily fixed in advance and cannot be chosen by the designer of the routing scheme. In case the addresses are initialized randomly, we show that two intervals per outgoing edge suffice, and, conversely, that two intervals are required for almost all graphs. Finally, if the node addresses can be chosen as desired, we show how to design in polynomial time a shortest path interval routing with a single interval per outgoing edge for all but at most O(log 3 n ) outgoing edges in each node. It follows that almost all graphs support a shortest path routing scheme which requires at most n+O(log 4 n ) bits of routing information per node, improving on the previous upper bound.

The purpose of compact routing is to provide a labeling of the nodes of a network, and a way to encode the routing tables so that routing can be performed efficiently (e.g., on shortest paths) while keeping the memory-space required to store the routing tables as small as possible. In this paper, we answer a long-standing conjecture by showing that compact routing can also help to perform distributed computations. In particular, we show that a network supporting a shortest path interval routing scheme allows to broadcast with an O(n) message-complexity, where n is the number of nodes of the network. As a consequence, we prove that O(n) messages suffice to solve leader-election for any graph labeled by a shortest path interval routing scheme, improving therefore the O(m + n) previous known bound.

In this paper we deal with interval routing on n-node networks of diameter D. We show that for every fixed D ≥ 2, there exists a network on which every interval routing scheme with O(n/log n) intervals per link has a routing path length at least [3D/2] - 1. It improves the lower bound on the routing path lengths for the range of very large number of intervals. No result was known about the path lengths when ever more than θ(√n) intervals per link was used. Best-known lower bounds for a small number of intervals are 2D-O(1) for 1 interval [11], and 3D/2 - O(1) up to θ(√n) intervals [5]. For D = 2, we show a network on which any interval routing scheme using less than n/4 - o(n) intervals has a routing path of length at least 3. Moreover, we build a network of bounded degree on which every interval routing scheme with routing path lengths bounded by 3D/2 - o(D) requires Ω(n/log2+en) intervals per link, where e is an arbitrary non-negative constant.

The compactness of a graph measures the space complexity of its shortest path routing tables. Each outgoing edge of a node x is assigned a (pairwise disjoint) set of addresses, such that the unique outgoing edge containing the address of a node y is the first edge of a shortest path from x to y. The complexity measure used in the context of interval routing is the minimum number of intervals of consecutive addresses needed to represent each such set, minimized over all possible choices of addresses and all choices of shortest paths. This paper establishes asymptotically tight bounds of n/4on the compactness of an n-node graph. More specifically, it is shown that every n-node graph has compactness at most n/4+o(n), and conversely, there exists an n-node graph whose compactness is n/4 - o(n). Both bounds improve upon known results. (A preliminary version of the lower bound has been partially published in Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, Lecture Notes in Comput. Sci. 1300, pp. 259--268, 1997.)

This paper presents a routing strategy called Pivot Interval Routing (PIR), which allows inessage routing on every weighted n-node network along paths whose stretch (namely, the ratio between their length and the distance between their endpoints) is at most five, and whose average stretch is at inost three, with routing tables of size O(n3/" log3/' n) bits in total.A similar routing strategy for unweighted networks which guarantees the same bounds on the stretch factor and in addition a bound of r1.501 on the route lengths, where D is the dianreter of the network, is also presented.Moreover, it is shown that the PIR strategy can be implemented so that the generated scheme is in the forin of an interval routing scheme (IRS), using at most 2dm intervals per link in the first case and 3,/m in the second case.As a result, the scheines are siinpler than previous ones and they imply that paths of messages are loop-free.Finally, it is showu that there is no loop-free routing strategy guaranteeing a inemory bound of J5i bits per router for all networks, regardless of the route lengths.

In this paper, we deal with the compact routing problem on distributed networks, that is implementing routing schemes that use a minimum memory size on each node.We prove that for every shortest path routing scheme, for any constant e, O < c < 1, and for every integer d such that 3 ~d < En, there exists a n-node network of maximum degree d that locally requires @(n log d) bits of memory on El(n) nodes.This optimal lower bound means that whatever you choose the routing scheme (interval routing, boolean routing, prefix routing, ...).there exists a network on which one can not do better than routing tables.

Article Local memory requirement of universal routing schemes Share on Authors: Pierre Fraigniaud Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, FranceView Profile , Cyril Gavoille Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, France Laboratoire de l'Informatique du Parallélisme - CNRS École Normale Supérieure de Lyon, 69364 Lyon cedex 07, FranceView Profile Authors Info & Claims SPAA '96: Proceedings of the eighth annual ACM symposium on Parallel Algorithms and ArchitecturesJune 1996 Pages 183–188https://doi.org/10.1145/237502.237541Published:24 June 1996 9citation144DownloadsMetricsTotal Citations9Total Downloads144Last 12 Months0Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

In this paper, we deal with the compact routing problem, that is implementing routing schemes that use a minimum memory size on each router. In [20], Peleg and Upfal showed that there is no hope to do that with less than a total \\Omega\\Gamma n 1+1=(2s+4) ) memory bits for any stretch factor s 1. We improve this bound for stretch factors s ! 2 by proving that any near-shortest path routing scheme uses a total of \\Omega\\Gamma n 2 ) memory bits.

Compact routing tables are useful to implement routing algorithms on a distributed memory parallel computer. Interval routing is a popular way of building such compact tables. It was already known that any network can support an interval routing function with only one interval per output port as soon as one allows intervals to be "cyclic" [13]. However, it might be interesting for practical reasons to allow only the use of "linear" intervals (see [2]). This notion is particularly useful to derive results on networks built by cartesian products (as hypercubes and torus) [4]. In this paper, we characterize the networks that admit a linear interval routing function with at most one interval per output port. We also characterize the networks that admit a strict linear interval routing function with at most one interval per output port.