The use of Low Earth orbit satellites (LEO) for communication has become a reality (e.g., SpaceX). The usage of Internet communication for communicating videos is very significant. We propose a scheme based on Scalable Video Coding (SVC) that fits multicast to users with heterogeneous resolution demands (e.g., mobile phones, computer screens, and HD televisions). The use of SVC allows a significant reduction in the total communicated information, typically a reduction of dozens of percentages. We build a hierarchy of optimal Steiner trees to communicate the video-encoded layers of the SVC. The first Steiner tree spans across all the terminals and is used to convey the first layer of the SVC, and the second spans the terminals that require more resolution than the basic resolution. The third Steiner tree spans the terminals that require even more resolution, and so forth for the following Steiner trees and SVC layers. We suggest a new algorithm for finding the Steiner trees in the hierarchy, such that they are all optimal and prefer edges not used by the Steiner trees that are used for previous layers. Thus, communication can be distributed without sacrificing optimality.

The longest simple path and snake-in-a-box are combinatorial search problems of considerable research interest. Recent work has recast these problems as special cases of a generalized longest simple path (GLSP) framework, and showed how to generate improved search heuristics for them. The greatest reduction in search effort was based on SPQR tree rules, but it was posed as an open problem how to use them optimally. Unrelated to search, a theoretical paper on the existence of simple cycles that include three given edges answers such queries in linear time with SPQR trees. These theoretical results are utilized in this paper to develop advanced heuristics and search partitioning for GLSP. Empirical results on grid-based graphs show that these heuristics can result in orders of magnitude reduction in the number of expansions, as well as significantly reduced overall runtime in most cases.

We study the problem of seamlessly updating several routes in a network, in the context of Software-Defined Networking (SDN). A set of routes pairs (Ci, Ni) is given, where each new Nishould replace the existing Ci. We look for a way of gradual updating, so that routing cycles are never created during the replacement process. In that, we follow the recent paper of Delaet et al., which considered the case of updating a single route. In addition, we require avoiding congestion on links. We provide an example of several routes replacement, where the strategy suggested by Delaet et al. fails: it arrives at a deadlock, while a legal way of replacement exists. We suggest a dependence graph model for solving the problem. The dependence graph nodes are: a) the sub-routes resulting from sub-dividing all Niand Ciby the routers common to Niand Ci, and b) the potentially congested links. We define which new sub-routes are legal for replacement. Further, we describe the changes in routing and in the dependence graph resulting from launching a legal new subroute. Summarizing, we reduce the route replacement problem to finding an (optimal) sequence of launchings of currently legal new sub-routes, using the dynamic dependence graph. Moreover, we suggest a novel meta-approach for resolving deadlocks, by utilizing the optical wires that connect the SDN controller to the routers.

We show that for every n-point metric space M and positive integer k, there exists a spanning tree T with unweighted diameter O(k) and weight w(T) = O(k ldr n1/k)ldrw(MST(M)), and a spanning tree T' with weight w(T') = O(k)ldrw(MST(M)) and unweighted diameter O(k ldr n1/k). Moreover, there is a designated point rt such that for every other point v, both distT(rt, v) and distT(rt, v) are at most (1 + epsiv)ldrdistM(rt,v), for an arbitrarily small constant epsiv > 0. We prove that the above tradeoffs are tight up to constant factors in the entire range of parameters. Furthermore, our lower bounds apply to a basic one-dimensional Euclidean space. Finally, our lower bounds for the particular case of unweighted diameter O(log n) settle a long-standing open problem in Computational Geometry.

We consider a failure-free, asynchronous message passing network with n links, where the processors are arranged on a ring or a chain. The processors are identically programmed but have distinct identities, taken from {0, 1,… , M − 1}. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF (finding the maximum identity). We show that in chain and ring topologies, the message complexities of all three tasks are the same. Hence, we study a finer measure of complexity: the number of transmitted bits required to solve a task T , denoted BitC ( T ). We prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC (Consensus) = 2 and BitC (Leader) = BitC (MaxF) = 2log 2 M ± O (1), where the gap between the lower and upper bounds is almost always 1. For a chain, BitC (Consensus) = Θ( n ), BitC (Leader) = Θ( n + log M ), and BitC (MaxF) = Θ( n log M ). For the ring topology, we prove the lower bound of Ω( n log M ) for Leader, and (hence) MaxF. We consider also a chain where the intermediate processors have no identities. We prove that BitC (Leader) = Θ( n log M ), which is equal to n times the bit complexity of the problem for two processors. For the specific case when the chain length is even, we prove that BitC (Leader) = Θ( n ), for both above settings. In addition, we show that for any algorithm solving MaxF, there exists an input, for which every execution has the bit complexity Ω( n log M ) (this is not the case for Leader). In our proofs, we use both methods of distributed computing and of communication complexity theory, establishing new links between the two areas.

We study the Bottleneck Tower of Hanoi puzzle posed by D. Wood in 1981. There, a relaxed placement rule allows a larger disk to be placed higher than a smaller one if their size difference is less than a pregiven value k . A shortest sequence of moves (optimal algorithm) transferring all the disks placed on some peg in decreasing order of size, to another peg in the same order is in question. In 1992, D. Poole suggested a natural disk-moving strategy for this problem, and computed the length of the shortest move sequence under its framework. However, other strategies were overlooked, so the lower bound/optimality question remained open. In 1998, Benditkis, Berend, and Safro proved the optimality of Poole's algorithm for the first nontrivial case k = 2. We prove Poole's algorithm to be optimal in the general case.

Let G=(V,E) be an undirected graph, S be a subset of its vertices, ${\frak C}_S$ be the set of minimum edge-cuts partitioning S, and $\lambda_S$ be the cardinality of such a cut. We suggest a graph structure, called the connectivity carcass of S, that represents both cuts in $\frak C_S$ and the partition of V by all these cuts; its size is $O(\min\{|E|,\lambda_S|V|\})$. In this paper we present general constructions and study in detail the case $\lambda_S$ odd; the specifics of the case $\lambda_S$ even are considered elsewhere. For an adequate description of the connectivity carcass we introduce a new type of graph: locally orientable graphs, which generalize digraphs. The connectivity carcass consists of a locally orientable quotient graph of G, a cactus tree (in case $\lambda_S$ odd, just a tree) representing all distinct partitions of S by cuts in ${\frak C}_S$, and a mapping connecting them. One can build it in O(|S|) max-flow computations in G. For an arbitrary sequence of u edge insertions not changing $\lambda_S$, the connectivity carcass can be maintained in time $O(|V|\min\{|E|,\lambda_S|V|\}+u)$. For two vertices of G, queries asking whether they are separated by a cut in $\frak C_S$ are answered in O(1) worst-case time per query. Another possibility is to maintain the carcass in $O(|S|\min\{|E|,\lambda_S|V|\}+u)$ time, but to answer the queries in O(1) time only if at least one of the vertices belongs to S.

For the Butterfly of N input/output vertices we present a layout on the square grid of area k N2 + o(N').A lower bound of the same order is proved.The encompassing rectangle which defines the area is 45' slanted w.r.t. the grid axes and the input/output vertices are not on the boundary of this rectangle.For the Butterfly of A4 input/output edges we present a layout of area +M" + o(M').In this layout the input edges are on the 1.h.s. of the upright encompassing rectangle and the output edges are on its r.h.s.Again this is also a lower bound.Both layouts are scalable.i.e. if one allocates for each switch a square of Q x a area, the layouts remain of area f N2 + o( N2) and iA4' + o(M'), respectively, where the value of a affects only the o(N2) and o(A4') terms.Both layouts are free of knock-knees.

Ye m Dinitz Shlomo Moran Sergio Rajsbaum Abstract We consider a failure-free, asynchronous message passing network, with n processors arranged on a ring or a chain. The processes are identically programmed but have distinct identities, taken from f1; : : : ; Mg. We investigate the communication costs of three well studied tasks: Consensus, Leader, and MaxF ( nding the maximum identity, a restricted version of Leader). We show that in both chain and ring topologies, somewhat surprisingly, the message complexities of all three tasks are the same. Hence, we suggest as a ner measure of complexity the number of bits transmitted, BitC(). We show that in chains, w.r.t. this measure, Consensus is easier than Leader, which is easier than MaxF. More speci cally, we prove several new lower bounds (and some simple upper bounds) that imply the following results: For the two processors case, BitC(Consensus) = 2 and BitC(Leader) = BitC(MaxF) = 2 log 2 M O(1). For a chain, BitC(Consensus) = (n), and BitC(MaxF) = (n log M ). When the length is even BitC(Leader) = (n), while if the length is odd BitC(Leader) = (n + log M ).

Let G=(V,E) be a capacitated directed graph with a source s and k terminals t/sub i/ with demands d/sub i/, 1/spl les/i/spl les/k. We would like to concurrently route every demand on a single path from s to the corresponding terminal without violating the capacities. There are several interesting and important variations of this unsplittable flow problem. If the necessary cut condition is satisfied, we show how to compute an unsplittable flow satisfying the demands such that the total flow through any edge exceeds its capacity by at most the maximum demand. For graphs in which all capacities are at least the maximum demand, we therefore obtain an unsplittable flow with congestion at most 2, and this result is best possible. Furthermore, we show that all demands can be routed unsplittable in 5 rounds, i.e., all demands can be collectively satisfied by the union of 5 unsplittable flows. Finally, we show that 22.6% of the total demand can be satisfied unsplittably. These results are extended to the case when the cut condition is not necessarily satisfied. We derive a 2-approximation algorithm for congestion, a 5-approximation algorithm for the number of rounds and a 4.43=1/0.226-approximation algorithm for the maximum routable demand.

Article A 2-level cactus model for the system of minimum and minimum+1 edge-cuts in a graph and its incremental maintenance Share on Authors: Yefim Dinitz Dept. of Computer Science, Technion, Haifa, Israel Dept. of Computer Science, Technion, Haifa, IsraelView Profile , Zeev Nutov Dept. of Applied Mathematics, Technion, Haifa, Israel Dept. of Applied Mathematics, Technion, Haifa, IsraelView Profile Authors Info & Claims STOC '95: Proceedings of the twenty-seventh annual ACM symposium on Theory of computingMay 1995 Pages 509–518https://doi.org/10.1145/225058.225268Online:29 May 1995Publication History 11citation328DownloadsMetricsTotal Citations11Total Downloads328Last 12 Months18Last 6 weeks5 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

Article Free Access Share on The connectivity carcass of a vertex subset in a graph and its incremental maintenance Authors: Yefim Dinitz Department of Computer Science, Technion, Haifa, Israel and E. A. Dinic, MOSCOW Department of Computer Science, Technion, Haifa, Israel and E. A. Dinic, MOSCOWView Profile , Alek Vainshtein School of Mathematical Sciences, Tel-Aviv University, Ramat Aviv, Israel and Technion Israel School of Mathematical Sciences, Tel-Aviv University, Ramat Aviv, Israel and Technion IsraelView Profile Authors Info & Claims STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of ComputingMay 1994Pages 716–725https://doi.org/10.1145/195058.195442Published:23 May 1994Publication History 12citation362DownloadsMetricsTotal Citations12Total Downloads362Last 12 Months43Last 6 weeks4 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 SiteeReaderPDF