Monotony properties of connected visible graph searching

Search games are attractive for their correspondence with classical width parameters. For instance, the invisible search number (a.k.a. node search number) of a graph is equal to its pathwidth plus 1, and the visible search number of a graph is equal to its treewidth plus 1. The connected variants of these games ask for search strategies that are connected, i.e., at every step of the strategy, the searched part of the graph induces a connected subgraph. We focus on monotone search strategies, i.e., strategies for which every node is searched exactly once. The monotone connected visible search number of an n-node graph is at most O(logn) times its visible search number. First, we prove that this logarithmic bound is tight. Precisely, we prove that there is an infinite family of graphs for which the ratio monotone connected visible search number over visible search number is Ω(logn). Second, we prove that, as opposed to the non-connected variant of visible graph searching, “recontamination helps” for connected visible search. Precisely, we prove that, for any k4, there exists a graph with connected visible search number at most k, and monotone connected visible search number >k     

Nondeterministic Graph Searching: From Pathwidth to Treewidth

We introduce nondeterministic graph searching with a controlled amount of nondeterminism and show how this new tool can be used in algorithm design and combinatorial analysis applying to both pathwidth and treewidth. We prove equivalence between this game-theoretic approach and graph decompositions called q -branched tree decompositions, which can be interpreted as a parameterized version of tree decompositions. Path decomposition and (standard) tree decomposition are two extreme cases of q-branched tree decompositions. The equivalence between nondeterministic graph searching and q-branched tree decomposition enables us to design an exact (exponential time) algorithm computing q-branched treewidth for all q≥0, which is thus valid for both treewidth and pathwidth. This algorithm performs as fast as the best known exact algorithm for pathwidth. Conversely, this equivalence also enables us to design a lower bound on the amount of nondeterminism required to search a graph with the minimum number of searchers. Additional support of F.V. Fomin by the Research Council of Norway. Additional supports of P. Fraigniaud from the INRIA Project “Grand Large”, and from the Project PairAPair of the ACI “Masse de Données”. Additional supports of N. Nisse from the Project Fragile of the ACI “Sécurité & Informatique”.     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Optimized broadcasting and multicasting protocols in cut-throughrouted networks

This paper addresses the one-to-all broadcasting problem and the one-to-many broadcasting problem, usually simply called broadcasting and multicasting, respectively. Broadcasting is the information dissemination problem in which a node of a network sends the same piece of information to all the other nodes. Multicasting is a partial broadcasting in the sense that only a subset of nodes forms the destination set. Both operations have many applications in parallel and distributed computing. In this paper, we study these problems in both line model, and cut-through model. The former assumes long distance calls between nonneighboring processors. The latter strengthens the line model by taking into account the use of a routing function. Long distance calls are possible in circuit-switched and wormhole-routed networks, and also in many networks supporting optical facilities. In the line model, it is well known that one can compute in polynomial time a [log₂n]-round broadcast or multicast protocol for any arbitrary network. Unfortunately such a protocol is often inefficient from a practical point of view because it does not use the resources of the network in a balanced way. In this paper, we present a new algorithm to compute broadcast or multicast protocols. This algorithm applies under both line and cut-through models. Moreover, it returns protocols that efficiently use the bandwidth of the network. From a complexity point of view, we also show that most of the optimization problems relative to the maximization of the efficiency of broadcast or multicast protocols in terms of switching time or vertex load are NP-complete. We have, however, derived polynomial efficient solutions for tree-networks     

Interval Routing Schemes

Interval routing was introduced to reduce the size of routing tables: a router finds the direction where to forward a message by determining which interval contains the destination address of the message, each interval being associated to one particular direction. This way of implementing a routing function is quite attractive but very little is known about the topological properties that must satisfy a network to support an interval routing function with particular constraints (shortest paths, limited number of intervals associated to each direction, etc.). In this paper we investigate the study of the interval routing functions. In particular, we characterize the set of networks which support a linear or a linear strict interval routing function with only one interval per direction. We also derive practical tools to measure the efficiency of an interval routing function (number of intervals, length of the paths, etc.), and we describe large classes of networks which support optimal (linear) interval routing functions. Finally, we derive the main properties satisfied by the popular networks used to interconnect processors in a distributed memory parallel computer. Received February 7, 1996; revised November 25, 1996.     

Locality and checkability in wait-free computing

This paper studies notions of locality that are inherent to the specification of distributed tasks by identifying fundamental relationships between the various scales of computation, from the individual process to the whole system. A locality property called projection-closed is identified. This property completely characterizes tasks that are wait-free checkable, where a task $T =(\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be checkable if there exists a distributed algorithm that, given $s\in \mathcal{I }$ s ∈ I and $t\in \mathcal{O }$ t ∈ O , determines whether $t\in \varDelta {(s)}$ t ∈ Δ ( s ) , i.e., whether $t$ t is a valid output for $s$ s according to the specification of $T$ T . Projection-closed tasks are proved to form a rich class of tasks. In particular, determining whether a projection-closed task is wait-free solvable is shown to be undecidable. A stronger notion of locality is identified by considering tasks whose outputs “look identical” to the inputs at every process: a task $T= (\mathcal{I },\mathcal{O },\varDelta )$ T = ( I , O , Δ ) is said to be locality-preserving if $\mathcal{O }$ O is a covering complex of $\mathcal{I }$ I . We show that this topological property yields obstacles for wait-free solvability different in nature from the classical impossibility results. On the other hand, locality-preserving tasks are projection-closed, and thus they are wait-free checkable. A classification of locality-preserving tasks in term of their relative computational power is provided. This is achieved by defining a correspondence between subgroups of the edgepath group of an input complex and locality-preserving tasks. This correspondence enables to demonstrate the existence of hierarchies of locality-preserving tasks, each one containing, at the top, the universal task (induced by the universal covering complex), and, at the bottom, the trivial identity task.     

Scattering on a ring of processors

In this note, we prove that the complexity of scattering in an oriented ring of p processors is (p - 1) (β + Lτ) where L is the length of the messages, β the communication startup, and τ the elemental propagation time.