To find a maximum number of communication requests that can be satisfied concurrently, is a fundamental network scheduling problem. In this work we investigate the problem of finding a maximum number of multicast requests that can be scheduled simultaneously in a tree network in which the edges and links have heterogeneous bandwidth limitations.This problem generalizes two problems studied in the literature: maximum k-colorable subgraph in chordal graphs, maximum multi-commodity flow in trees. The problem is NP-hard and admits a 1.585-approximation in the special case of homogeneous bandwidth limitations.We first show that the problem is harder to approximate when the bandwidth limitations are heterogeneous, i.e. vary from link to link and from node to node. We then generalize of a classical algorithm and obtain an M-approximation where M is the maximum number of leaves of the communication subtrees. Surprisingly, variants of the same algorithm, are used in the literature at least four times to solve related problems. There exists a polynomial-time algorithm for the special case of unicast requests and star topology. We generalize this result and relax the second requirement so that the set of unicast requests share a common vertex with no restriction on the tree topology.

We consider the online version of the coalition structure generation problem, in which agents, corresponding to the vertices of a graph, appear in an online fashion and have to be partitioned into coalitions by an authority (i.e., an online algorithm). When an agent appears, the algorithm has to decide whether to put the agent into an existing coalition or to create a new one containing, at this moment, only her. The decision is irrevocable. The objective is partitioning agents into coalitions so as to maximize the resulting social welfare that is the sum of all coalition values. We consider two cases for the value of a coalition: (1) the sum of the weights of its edges, and (2) the sum of the weights of its edges divided by its size. Coalition structures appear in a variety of application in AI, multi-agent systems, networks, as well as in social networks, data analysis, computational biology, game theory, and scheduling. For each of the coalition value functions we consider the bounded and unbounded cases depending on whether or not the size of a coalition can exceed a given value α. Furthermore, we consider the case of a limited number of coalitions and various weight functions for the edges, i.e., unrestricted, positive and constant weights. We show tight or nearly tight bounds for the competitive ratio in each case.

Internet is growing rapidly in the developing world now. Stringent budget constraints give rise to networks with tree topology, leaving lesser room to apply energy savings methods proposed in the last decade as there are no redundant links or nodes in the network. In this paper, we propose SLEEPWELL, design of energy efficient network topology using energy aware networking devices. We divide users according to their profile of network usage and users with similar profile are all connected to one switch to allow the switch to sleep. We evaluate our framework using real data collected from the Local Area Network of IIT Kanpur (an Indian university) having more than ten thousand network users. Results show that even in a tree topology, SLEEPWELL achieves substantial energy gains, up to 22% using energy-efficient hardware, without compromising performance. We also show that dividing users in just two profiles accounts for more than 90% of the total energy saved using SLEEPWELL. We also evaluate the overheads occurred and show that the extra cost incurred can be recovered within two years for most of the practical scenarios.

Tolerance graphs have been extensively studied since their introduction, due to their interesting structure and their numerous applications, as they generalize both interval and permutation graphs in a natural way. It has been conjectured by Golumbic, Monma, and Trotter in 1984 that the intersection of tolerance and cocomparability graphs coincides with bounded tolerance graphs. Since cocomparability graphs can be efficiently recognized, a positive answer to this conjecture in the general case would enable us to efficiently distinguish between tolerance and bounded tolerance graphs, although it is NP-complete to recognize each of these classes of graphs separately. This longstanding conjecture has been proved under some– rather strong – structural assumptions on the input graph; in particular, it has been proved for complements of trees, and later extended to complements of bipartite graphs, and these are the only known results so far. Furthermore, it is known that the intersection of tolerance and cocomparability graphs is contained in the class of trapezoid graphs. Our main result in this article is that the above conjecture is true for every graph G that admits a tolerance representation with exactly one unbounded vertex; note that this assumption concerns only the given tolerance representation R of G , rather than any structural property of G . Moreover, our results imply as a corollary that the conjecture of Golumbic, Monma, and Trotter is true for every graph G = ( V , E ) that has no three independent vertices a , b , c ∈ V such that N ( a ) ⊂ N ( b ) ⊂ N ( c ) , where N ( v ) denotes the set of neighbors of a vertex v ∈ V ; this is satisfied in particular when G is the complement of a triangle-free graph (which also implies the above-mentioned correctness for complements of bipartite graphs). Our proofs are constructive, in the sense that, given a tolerance representation R of a graph G , we transform R into a bounded tolerance representation R ∗ of G . Furthermore, we conjecture that any minimal tolerance graph G that is not a bounded tolerance graph, has a tolerance representation with exactly one unbounded vertex. Our results imply the non-trivial result that, in order to prove the conjecture of Golumbic, Monma, and Trotter, it suffices to prove our conjecture.

Opportunistic traffic offloading has been proposed to tackle overload problems in cellular networks. However, existing proposals only address device-to-device-based offloading techniques with deadline-based data propagation, and neglect content injection procedures. In contrast, we tackle the offloading issue from another perspective: the base station interference coordination problem during content injection. In particular, we focus on dissemination of contents, and aim at the minimization of the total transmission time spent by base stations to inject the contents into the network. We leverage the almost blank sub-frame technique to keep under control the intercell interference in such a process. We formulate an optimization problem, prove that it is NP-hard and NP-complete, and propose a near-optimal heuristic to solve it. Our algorithm substantially outperforms classical intercell interference approaches, as we evaluate through the simulation of LTE-A networks.

Opportunistic traffic offloading has been proposed to tackle overload problems in cellular networks. However, they only address the problem of deadline-based content propagation in the cellular system, given wireless environment characterization. In contrast, we cope with the traffic offloading issue from another perspective: the base station interference coordination problem. In particular, we aim at the minimization of the total transmission time spent by the base stations in order to inject contents into the network, and we leverage the recently proposed ABSF technique to keep under control intercell interference. We formulate an optimization problem, prove that it is NP-Complete, and propose a near-optimal heuristic. Our proposed algorithm substantially outperforms classical intercell interference approaches proposed in the literature, as we evaluate through the simulation of dense LTE-A network scenarios.

All-optical networks have been largely investigated due to their high data transmission rates. In the traditional Wavelength-Division Multiplexing (WDM) technology, the spectrum of light that can be transmitted through the optical fiber has been divided into frequency intervals of fixed width, with a gap of unused frequencies between them. Recently, an alternative emerging architecture was suggested which moves away from the rigid Dense WDM (DWDM) model towards a flexible model, where usable frequency intervals are of variable width (even within the same link). Each light path has to be assigned a frequency interval (sub-spectrum), which remains fixed through all of the links it traverses. Two different light paths using the same link must be assigned disjoint sub-spectra. This technology is termed flex-grid (or, flex-spectrum), as opposed to fixed-grid (or, fixed-spectrum) current technology. In this work we study a problem of optimal bandwidth allocation arising in the flex-grid technology. In this setting, each light path has a lower and upper bound on the width of its frequency interval, as well as an associated profit, and we want to find a bandwidth assignment that maximizes the total profit. This problem is known to be NP-Complete. We observe that, in fact, the problem is inapproximable within any constant ratio even on a path network. We further derive NP-hardness results and present approximation algorithms for several special cases of the path and ring networks, which are of practical interest. Finally, while in general our problem is hard to approximate, we show that an optimal solution can be obtained by allowing resource augmentation. Our study has applications also in real time scheduling.

We consider the following fundamental scheduling problem in which the input consists of n jobs to be scheduled on a set of identical machines of bounded capacity g (which is the maximal number of jobs that can be processed simultaneously by a single machine). Each job is associated with a start time and a completion time, it is supposed to be processed from the start time to the completion time (and in one of our extensions it has to be scheduled also in a continuous number of days, this corresponds to a two-dimensional version of the problem). We consider two versions of the problem. In the scheduling minimization version the goal is to minimize the total busy time of machines used to schedule all jobs. In the resource allocation maximization version the goal is to maximize the number of jobs that are scheduled for processing under a budget constraint given in terms of busy time. This is the first study of the maximization version of the problem. The minimization problem is known to be NP-Hard, thus the maximization problem is also NP-Hard. We consider various special cases, identify cases where an optimal solution can be computed in polynomial time, and mainly provide constant factor approximation algorithms for both minimization and maximization problems. Some of our results improve upon the best known results for this job scheduling problem. Our study has applications in power consumption, cloud computing and optimizing switching cost of optical networks.

The placement of regenerators in optical networks has become an active area of research during the last few years. Given a set of lightpaths in a network$G$and a positive integer$d$, regenerators must be placed in such a way that in any lightpath there are no more than$d$hops without meeting a regenerator. The cost function we consider is given by the total number of regenerators placed at the nodes, which we believe to be a more accurate estimation of the real cost of the network than the number of locations considered in the work of Flammini(IEEE/ACM Trans. Netw., vol. 19, no. 2, pp. 498–511, Apr. 2011). Furthermore, in our model we assume that we are given a finite set of$p$possible traffic patterns (each given by a set of lightpaths), and our objective is to place the minimum number of regenerators at the nodes so that each of the traffic patterns is satisfied. While this problem can be easily solved when$d=1$or$p=1$, we prove that for any fixed$d,p \geq 2$, it does not admit a PTAS, even if$G$has maximum degree at most 3 and the lightpaths have length$ {\cal O}(d)$. We complement this hardness result with a constant-factor approximation algorithm with ratio$\ln (d \cdot p)$. We then study the case where$G$is a path, proving that the problem is polynomial-time solvable for two particular families of instances. Finally, we generalize our model in two natural directions, which allows us to capture the model of Flamminias a particular case, and we settle some questions that were left open therein.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications (in bioinformatics, constraint-based temporal reasoning, resource allocation, and scheduling problems, among others). Several efficient algorithms for optimization problems that are NP-hard in general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs—namely, the problem of deciding whether a given graph is a tolerance graph—as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf. the book on tolerance graphs [M. C. Golumbic and A. N. Trenk, Tolerance Graphs, Cambridge Stud. Adv. Math. 89, Cambridge University Press, Cambridge, UK, 2004]) since their introduction in 1982 [M. C. Golumbic and C. L. Monma, Proceedings of the 13th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congr. Numer., 35 (1982), pp. 321–331]. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an acyclic orientation of permutation and trapezoid graphs. Our main tool is a new algorithm that uses vertex splitting to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it was also proved a powerful tool in the design of efficient recognition algorithms for other classes of graphs [G. B. Mertzios and D. G. Corneil, Discrete Appl. Math., 159 (2011), pp. 1131–1147].

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem, we are given a network with an underlying topology of a graphGand with a set of requests that correspond to paths inG. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this paper, we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-completeness results, approximation algorithms, and inapproximability results.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This subclass of perfect graphs has been extensively studied, due to both its interesting structure and its numerous applications. Several efficient algorithms for optimization problems that are NP-hard on general graphs have been designed for tolerance graphs. In spite of this, the recognition of tolerance graphs --~namely, the problem of deciding whether a given graph is a tolerance graph~-- as well as the recognition of their main subclass of bounded tolerance graphs, have been the most fundamental open problems on this class of graphs (cf.~the book on tolerance graphs~\cite{GolTol04}) since their introduction in 1982~\cite{GoMo82}. In this article we prove that both recognition problems are NP-complete, even in the case where the input graph is a trapezoid graph. The presented results are surprising because, on the one hand, most subclasses of perfect graphs admit polynomial recognition algorithms and, on the other hand, bounded tolerance graphs were believed to be efficiently recognizable as they are a natural special case of trapezoid graphs (which can be recognized in polynomial time) and share a very similar structure with them. For our reduction we extend the notion of an \emph{acyclic orientation} of permutation and trapezoid graphs. Our main tool is a new algorithm that uses \emph{vertex splitting} to transform a given trapezoid graph into a permutation graph, while preserving this new acyclic orientation property. This method of vertex splitting is of independent interest; very recently, it has been proved a powerful tool also in the design of efficient recognition algorithms for other classes of graphs~\cite{MC-Trapezoid}.

We consider a scheduling problem in which a bounded number of jobs can be processed simultaneously by a single machine. The input is a set of n jobs J = {J1,..., Jn}. Each job, Jj, is associated with an interval [sj, cj] along which it should be processed. Also given is the parallelism parameter g ges 1, which is the maximal number of jobs that can be processed simultaneously by a single machine. Each machine operates along a contiguous time interval, called its busy interval, which contains all the intervals corresponding to the jobs it processes. The goal is to assign the jobs to machines such that the total busy time of the machines is minimized. The problem is known to be NP-hard already for g = 2. We present a 4-approximation algorithm for general instances, and approximation algorithms with improved ratios for instances with bounded lengths, for instances where any two intervals intersect, and for instances where no interval is properly contained in another. Our study has important application in optimizing the switching costs of optical networks.

Placement of regenerators in optical networks has attracted the attention of recent research works in optical networks. In this problem we are given a network, with an underlying topology of a graph G, and with a set of requests that correspond to paths in G. There is a need to put a regenerator every certain distance, because of a decrease in the power of the signal. In this work we investigate the problem of minimizing the number of locations to place the regenerators. We present analytical results regarding the complexity of this problem, in four cases, depending on whether or not there is a bound on the number of regenerators at each node, and depending on whether or not the routing is given or only the requests are given (and part of the solution is also to determine the actual routing). These results include polynomial time algorithms, NP-complete results, approximation algorithms, and inapproximability results.

We apply the tree-pattern enumeration formulæof earlier work of ours [N. Dershowitz and S. Zaks, Discrete Appl. Math., 25 (1989), pp. 241–255], and a new extension thereof, to some recent enumerations of distributions of leaves in ordered trees [W. Y. C. Chen, E. Deutsch, and S. Elizalde, European J. Combin., 27 (2006), pp. 414–427] and in bicolored ordered trees [L. H. Clark, J. E. McCanna, and L. A. Székely, Bull. Inst. Combin. Appl., 21 (1997), pp. 33–45], and of distributions of up-down-up subpaths in Dyck lattice paths [Y. Sun, Discrete Math., 287 (2004), pp. 177–186]. Bijections are used to facilitate the derivation of statistics for bicolored trees.

Tolerance graphs model interval relations in such a way that intervals can tolerate a certain degree of overlap without being in conflict. This class of graphs, which generalizes in a natural way both interval and permutation graphs, has attracted many research efforts since their introduction in [M. C. Golumbic and C. L. Monma, Congr. Numer., 35 (1982), pp. 321–331], as it finds many important applications in constraint-based temporal reasoning, resource allocation, and scheduling problems, among others. In this article we propose the first non-trivial intersection model for general tolerance graphs, given by three-dimensional parallelepipeds, which extends the widely known intersection model of parallelograms in the plane that characterizes the class of bounded tolerance graphs. Apart from being important on its own, this new representation also enables us to improve the time complexity of three problems on tolerance graphs. Namely, we present optimal $\mathcal{O}(n\log n)$ algorithms for computing a minimum coloring and a maximum clique and an $\mathcal{O}(n^{2})$ algorithm for computing a maximum weight independent set in a tolerance graph with n vertices, thus improving the best known running times $\mathcal{O}(n^{2})$ and $\mathcal{O}(n^{3})$ for these problems, respectively.

SONET ADMs are dominant cost factors in WDM/SONET rings. Whereas most previous papers on the topic concentrated on the number of wavelengths assigned to a given set of lightpaths, more recent papers argue that the number of ADMs is a more realistic cost measure. Some of these works discuss various heuristic algorithms for this problem, and the best known result is a 3/2 approximation in G. Calinescu and P.J. Wan (2001). Through the study of the relation between this problem and the problem of finding maximum disjoint rings in a given set of lightpaths we manage to shed more light onto this problem and to develop a 10/7 + /spl epsi/ approximation for it.

This paper studies the design of low-cost survivable wavelength-division-multiplexing (WDM) networks. To achieve survivability, lightpaths are arranged as a set of rings. Arrangement in rings is also necessary to support SONET/SDH protection schemes such as 4FBLSR above the optical layer. This is expected to be the most common architecture in regional (metro) networks. We assume that we are given a set of lightpaths in an arbitrary network topology and aim at finding a partition of the lightpaths to rings adding a minimum number of lightpaths to the original set. The cost measure that we consider (number of lightpaths) reflects the switching cost of the entire network. In the case of a SONET/SDH higher layer, the number of lightpaths is equal to the number of add-drop multiplexers (ADMs) (since two subsequent lightpaths in a ring can share an ADM at the common node). We prove some negative results on the tractability and approximability of the problem and provide an approximation algorithm with a worst case approximation ratio of 8/5. We study some special cases in which the performance of the algorithm is improved. A similar problem was introduced, motivated, and studied by Liu, Li, Wan and Frieder (see Proc. INFOCOM 2000, p.1020-1025, 2000) Gerstel, Lin and Sasaki, (see Proc. IEEE INFOCOM '98, p. 94-101, 1998)(where it was termed minimum ADM problem). However, these two works focused on a ring topology while we generalize the problem to an arbitrary network topology.

Linear interval routing is a space-efficient routing method for point-to-point communication networks. It is a restricted variant of interval routing where the routing range associated with every link is represented by an interval with no wraparound. A common way to measure the efficiency of such routing methods is in terms of the maximal length of a path a message traverses. For interval routing, the upper bound and lower bound on this quantity are 2D and 2D − 3, respectively, where D is the diameter of the network. We prove a lower bound of Ω(D2) on the length of a path a message traverses under linear interval routing. We further extend the result by showing a connection between the efficiency of linear interval routing and the total2-diameter (defined in Section 4) of the network, and by presenting a family of graphs for which this lower bound is tight. © 1999 John Wiley & Sons, Inc. Networks 34: 37–46, 1999

We present a new network design problem that is applicable for designing virtual paths (VPs) in an asynchronous transfer mode (ATM) network to efficiently support client/server applications. We present several alternatives for the solution, compare their properties, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). We also present simulation results that demonstrate the performance and scalability of our solution. In addition, we propose a new efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks.

We present a new network design problem that arises when designing virtual paths in an ATM network to properly support client/server applications. We present several alternatives for the solution, discuss their pros and cons, and focus on a novel "greedy" solution, which we prove to optimize certain important criteria (namely, the network overhead for a request/response and the utilization of bandwidth and routing table resources). In addition, we propose a new, efficient bandwidth allocation scheme which is tailored for client/server applications over ATM networks. The results in this work imply the importance of ATM switches that switch both VPs and VCs.

We study the problem of designing a layout of virtual paths (VPs) on a given ATM network. We first define a mathematical model that captures the characteristics of virtual paths. In this model, we define the general VP layout problem, and a more restricted case; while the general case layout should cater connections between any pair of nodes in the network, the restricted case layout should only cater connections between a specific node to the other nodes. For the latter case, we present an algorithm that finds a layout by decomposing the network into subnetworks and operating on each subnetwork, recursively; we prove an upper bound on the optimality of the resulting layout and a matching lower bound for the problem, that are tight under certain realistic assumptions. Finally, we show how the solution for the restricted case is used as a building block in various solutions to more general cases (trees, meshes, K-separable networks, and general topology networks) and prove a lower bound for some of our results. The results exhibit a tradeoff between the efficiency of the call setup and both the utilization of the VP routing tables and the overhead during recovery from link disconnections.

In th~paper we present a new model, within which we define a generrd routing problem (termed virtual path layout) that occurs in fast networks (ATM).In an effort to solve this general problem, we first define an intermediate problem, and prove it is NPcomplete.We then restrict some of the assumptions to yield a practical subproblem, for which we present a polynomial time greedy algorithm, that produces an optimal solution.Finally, we solve the general problem using the polynomially solvable subproblem as a building block.The results exhibit a tradeoff between the performance of a routing scheme and its resource utilization.

Abstract A new characterization of tree medians is presented: We show that a vertex m is a median of a tree T with n vertices iff there exists a partition of the vertex set into [n/2] disjoint pairs (excluding m when n is odd), such that all the paths connecting the two vertices in any of the pairs pass through m. We show that in this case the sum of the distances between these pairs of vertices is the largest possible among all such partitions, and we use this fact to discuss lower bounds on the message complexity of the distributed sorting problem. We show that, given a network of a tree topology, choosing a median and then routing all the information through it is the best possible strategy, in terms of worst‐case number of messages sent during any execution of any distributed sorting algorithm. We also discuss the implications for networks of a general topology and for the distributed ranking problem. © 1994 by John Wiley & Sons, Inc.

Chou et al. (1990) presented two synchronizer algorithms for ABD networks. One of their synchronizers has a round time of three, and the other has a round time of only two but requires an additional bit in every message of the simulated algorithm. The authors show that ABD synchronization can be improved by using information that can be obtained, without exchanging more messages, during the initialization of the synchronizers. The authors first contribution is a synchronizer with a round time of two that does not require an additional bit in basic messages. The second result refutes the common belief that a round time of two is the best achievable for this type of synchronizer. They show that in some network topologies a smaller round time is achievable by making the local time of simulation of the pulses dependent on the arrival time of messages received during initialization. The correctness of the synchronizers is shown by modeling this class of synchronizers as functions, and using these functions lower bounds on the round time can also be easily obtained. The authors show that their synchronizers are optimal, i.e., further reduction of the round time by the same means is not possible.>

An efficient way to synchronize an asynchronous network with a bounded delay message delivery is presented. Two types of synchronization algorithm are presented. Both types require an initializing phase that costs mod E mod messages (where mod E mod is the number of links). The first requires an additional bit in every message and increases the time complexity by a factor of 2. The second does not require any additional bits but increases the time complexity by a factor of 3. How to overcome differences in nodal timer rates is explained.>

The problem of distributed leader election in an asynchronous complete network, in the presence of faults that occurred prior to the execution of the election algorithm, is discussed. Failures of this type are encountered, for example, during a recovery from a crash in the network. For a network with n processors, k of which start the algorithm that uses at most O(n log k+n+kt) messages is presented and shown to be optimal. An optimal algorithm for the case where the identities of the neighbors are known is also presented. It is noted that the order of the message complexity of a t-resilient algorithm is not always higher than that of a nonresilient one. The t-resilient algorithm is a systematic modification of an existing algorithm for a fault-free network.>

Fischer, Lynch and Paterson showed in a fundamental paper that achieving a distributed agreement for N > I processors is impossible in the presence of one faulty processor.This result was later extended by Moran and Wolfstahl who showed that it holds for any task with a connected input graph and a disconnected decision graph (whcrc a vcrtcx in the input [decision] graph is an N-tuple of input [decision] values of the processors, and there is an edge connecting two vertices if and only if they differ in exactly one component),In this paper we extend that latter result, and in fact we set the exact bordedine between solvable and unsolvable tasks, by giving a necessary and sufficient condition for a task to be solvable in the presence of a faulty processor.We present a universal protocol which solves any task which is found to be solvable by our condition.Using our characterization, we derive a novel technique to prove lower bounds on the number of messages that must be sent due to processor failure; specifically, we show that for each fixed JV > 2 there exist distributed tasks for Iv processors that can be solved in the presence of a faulty processor, but any protocol that solves them must send arbitrarily many messages in the worst case.

In a previous paper we showed that the distributive construction of a spanning tree in a complete network of processors can be done in $O(n\log n)$ messages. We show in this work that if the spanning tree is required to satisfy certain properties, then the complexity of its construction increases: First we show that the construction of a minimum weight spanning tree requires, in the worst case, at least $\Omega (n^2 )$ messages, and then we show that the construction of a spanning tree where the maximum degree is at most k may require at least $\Omega ({{n^2 } / k})$ messages in the worst case. Actually, in both cases the lower bounds are shown for the number of edges used in the worst case. Moreover, the results are valid for both asynchronous and synchronous networks, and are independent of the lengths of the messages. On the other hand, there are algorithms for the above tasks which achieve these lower bounds, up to a constant factor, and use messages of $O(\log n)$ length.

Abstract We study the bit complexity of pattern recognition in a distributed ring with a leader. Each processor gets as input a letter from some alphabet, and these concatenated letters, starting at the leader, form the pattern of the ring. The leader initiates an algorithm that accepts or rejects this pattern. Thus each algorithm recognizes a language over a given alphabet. We prove the following (n is the size of the ring, not known a priori to any of the processors): 1. (1) A language is recognized by an algorithm that uses O(n) bits if any only if it is regular. 2. (2) Every non-regular language requires at least Ω(n log n) bits for its recognition (clearly, every language requires no more than O(n2) bits for its recognition). 3. (3) For every function g(n), Ω(n log n)≤g(n)≤O(n 2 ) , there is a language that requires Θ(g(n)) bits for its recognition.

Article The optimality of distributive constructions of minimum weight and degree restricted spanning trees in a complete network of processors Share on Authors: E. Korach Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile , S. Moran Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile , S. Zaks Computer Science Department, Technion - Israel Institute of Technology, Haifa, Israel Computer Science Department, Technion - Israel Institute of Technology, Haifa, IsraelView Profile Authors Info & Claims PODC '85: Proceedings of the fourth annual ACM symposium on Principles of distributed computingAugust 1985 Pages 277–286https://doi.org/10.1145/323596.323622Online:01 August 1985Publication History 2citation186DownloadsMetricsTotal Citations2Total Downloads186Last 12 Months1Last 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

We study the problems of sorting and ranking n processors that have initial values (not necessarily distinct) in a distributed system. Sorting means that the initial values have to move around in the network and be assigned to the processors according to their distinct identities, while ranking means that the numbers 1, 2,..., n have to be assigned to the processors according to their initial values; ties between initial values can be broken in any chosen way. Assuming a tree network, and assuming that a message can contain an initial value, an identity, or a rank, we present an algorithm for the ranking problem that uses, in the worst case, at most n2/2+O(n) such messages. The algorithm is then extended to perform sorting, using in the worst case at most 3n2/4+O(n) messages. Both algorithms are using a total of O(n) space. The algorithms are extended to general networks. The expected behavior of these algorithms for three classes of trees is discussed. Assuming that the initial values, identities, and ranks can be compared only within themselves, lower bounds of n2/2 and 3n2/4 messages are proved for a worst case execution of any algorithm to solve the ranking and sorting problems, respectively.

Distributed algorithms for complete asynchronous networks of processors (i.e., networks where each pair of processors is connected by a communication line) are discussed. The main result is O(nlogn) lower and upper bounds on the number of messages required by any algorithm in a given class of distributed algorithms for such networks. This class includes algorithms for problems like finding a leader or constructing a spanning tree (as far as we know, all known algorithms for those problems may require O(n2) messages when applied to complete networks). O(n2) bounds for other problems, like constructing a maximal matching or a Hamiltonian circuit are also given. In proving the lower bound we are counting the edges which carry messages during the executions of the algorithms (ignoring the actually number of messages carried by each edge). Interestingly, this number is shown to be of the same order of magnitude of the total number of messages needed by these algorithms. In the upper bounds, the length of any message is at most log2[4mlog2n] bits, where m is the maximum identity of a node in the network. One implication of our results is that finding a spanning tree in a complete network is easier than finding a minimum weight spanning tree in such a network, which may require O(n2) messages.

We show a one-to-one correspondence between all the ordered trees that have $n_0 + 1$ leaves and $n_i $ internal nodes with $k_i $ sons each, for $i = 1, \cdots ,t$, (hence $n_0 = \sum_1^t (k_i - 1) n_i $) and all the lattice paths in the $(t + 1)$-dimensional space, from the point $(n_0 ,n_1 , \cdots , n_t )$ to the origin, which do not go below the hyperplane $x_0 = \sum_1^t (k_i - 1) x_i $. Procedures for generating these paths (and thus the ordered trees) are presented and the ranking and unranking procedures are derived.