Let G=(V,E) be an undirected graph on n vertices and λ:E→2N a mapping that assigns to every edge a non-empty set of integer labels (discrete times when the edge is present). Such a labelled graph G=(G,λ) is temporally connected if a path exists with non-decreasing times from every vertex to every other vertex. In a seminal paper, Kempe, Kleinberg, and Kumar [17] asked whether, given such a temporally connected graph, a sparse subset of edges always exists whose labels suffice to preserve temporal connectivity – a temporal spanner. Axiotis and Fotakis [5] answered negatively by exhibiting a family of Θ(n2)-dense temporal graphs which admit no temporal spanner of density o(n2). In this paper, we give the first positive answer as to the existence of o(n2)-sparse spanners in a dense class of temporal graphs, by showing (constructively) that if G is a complete graph, then one can always find a temporal spanner with O(nlog⁡n) edges.

For mobile multimedia systems, advances in battery technology have been much slower than those in memory, graphics, and processing power, making power consumption a major concern in mobile systems. The computational complexity of video codecs, which consists of CPU operations and memory accesses, is one of the main factors affecting power consumption. In this article, we propose a method that achieves near-optimal video quality while respecting user-defined bounds on the complexity needed to decode a video. We specifically focus on the motion compensation process, including motion vector prediction and interpolation, because it is the single largest component of computation-based power consumption. We start by formulating a scenario with a single receiver as a rate-distortion optimization problem and we develop an efficient decoder-complexity-aware video encoding method to solve it. Then we extend our approach to handle multiple heterogeneous receivers, each with a different complexity requirement. We test our method experimentally using the H.264 standard for the single receiver scenario and the H.264 SVC extension for the multiple receiver scenario. Our experimental results show that our method can achieve up to 97% of the optimal solution value in the single receiver scenario, and an average of 97% of the optimal solution value in the multiple receiver scenario. Furthermore, our tests with actual power measurements show a power saving of up to 23% at the decoder when the complexity threshold is halved in the encoder.

Advances in battery technology have not kept pace with other recent advances in mobile multimedia systems with the result that power consumption is a major concern. The computational complexity of video codecs, which consists of CPU operations and memory accesses, is one of the main factors affecting power consumption. In this paper, we propose a method that achieves good video quality while at the same time guaranteeing that the complexity needed to decode the video does not exceed a specific threshold defined by a user. We focus on the motion compensation process, including motion vector prediction and interpolation, which is the biggest single component in computation-based power consumption. We formulate the rate-distortion optimization problem and present an efficient method for decoder complexity-aware video encoding in the H.264 video codec. Our results show that our method can achieve up to 95% of the optimal solution value.

Advances in computing hardware and novel multimedia applications have urged the development of handheld mobile devices such as smartphones and PDAs. Amongst the most used applications on handheld devices are mobile 3D graphics such as 3D games and 3D virtual environments. With this significant increase of mobile applications and games, one of the challenges is how to efficiently transmit the bulky 3D information to resource-constrained mobile devices. Despite the many attractive features, 3D graphics impose significant demands on the limited battery capacity of mobile devices. Thus the development of efficient approaches to decrease the amount of streamed data with the aim of increasing the battery lifetime has become a key research topic.

We propose a novel algorithm to efficiently transmit multiple Variable-Bit-Rate (VBR) video streams from a base station to mobile receivers in wide-area wireless networks. The algorithm multicasts video streams in bursts to save the energy of mobile devices. In addition, the algorithm adaptively controls the buffer levels of mobile devices receiving different video streams according to the bit rate of the video stream being received by each device. Compared to previous algorithms, the new algorithm enables dynamic control of the wireless channel and allows the base station to transmit more video data on time to mobile receivers. This is done by providing finer control over the bandwidth allocation of the wireless channel. The problem of optimizing energy saving has been shown to be NP-Complete. We prove that our algorithm finds a feasible schedule if one exists and always produces a correct schedule even when dropped frames are unavoidable. We analytically bound the gap between the energy saving resulting from our algorithm and the optimal energy saving and show that our results are close to optimal. We analyze the tradeoff between the fine control over bandwidth allocation and energy saving and demonstrate that in practical situations, flexible and finer control of bandwidth allocation will result in significantly lower frame loss rates while achieving higher energy saving. We have implemented the proposed algorithm as well as two other recent algorithms in a mobile video streaming testbed. Our extensive analysis and results demonstrate that the proposed algorithm outperforms the other two algorithms; it results in higher energy saving for mobile devices and fewer dropped video frames.

Smartphone devices are becoming the de facto personal computing platform, rivaling the desktop, as the number of smartphone users is projected to reach 1.1 billion by 2013. Unlike the desktop, smartphones have a constrained energy budget, which is further challenged by increasingly sophisticated applications. Amongst the most popular applications on smartphone devices are games and virtual environments that rely on 3D graphics. Due to the computational intensity of geometry and rasterization, as well as the perpetually illuminated display, these applications are extremely power-hungry. To prolong the battery life of devices running these applications, we propose two new energy-aware adaptation schemes that can be employed in 3D graphics applications: lighting limitation and textural transformation. Our results show that we can conserve between 20% and 33% of energy with acceptable sacrifices to a user's visual experience.

This paper describes an experimental study that closely examines the underlying topologies of multiple complex networks formed in BitTorrent swarms. Our results demonstrate that the networks exhibit fundamental differences during different stages of a swarm, suggesting that the initial stage is not predictive of the overall performance. We also find a power-law degree distribution in the network of peers that are unchoked by others, which indicates the presence of a robust scale-free network. However, unlike previous studies, we find no clear evidence of persistent clustering in any of the networks, precluding the presence of a small-world that is potentially efficient for peer-to-peer downloading. These results suggest an interesting venue for improving BitTorrent's performance. We present a first attempt to introduce clustering into BitTorrent. Our approach is theoretically proven and makes minimal changes to the tracker only. Its effectiveness is verified through a series of simulations and experiments.

In the broadcasting problem, one node needs to broadcast a message to all other nodes in a network. If nodes can only communicate with one neighbor at a time, broadcasting takes at least $\lceil \log_2 N \rceil$ rounds in a network of N nodes. In the neighborhood broadcasting problem, the node that is broadcasting needs to inform only its neighbors. In a binary hypercube with N nodes, each node has $\log_2 N$ neighbors, so neighborhood broadcasting takes at least $\lceil \log_2 \log_2 (N+1) \rceil$ rounds. In this paper, we present asymptotically optimal neighborhood broadcast protocols for binary hypercubes.

Broadcast is the fundamental collective communication routine in which the same message is delivered from a single source to all the nodes in a network. The most efficient way to implement broadcast is through the construction of a broadcast tree. We introduce a revised definition of optimality for the i-port model broadcast tree based on fault-tolerance, and we construct optimal broadcast trees for interconnection networks modeled by Double Loop-Graphs for 1 ≤ i ≤ 4. © 2005 Wiley Periodicals, Inc. NETWORKS, Vol. 46(2), 88–97 2005

Abstract Gossiping is an information dissemination problem in which each node of a communication network has a unique piece of information that must be transmitted to all other nodes using two‐way communications between pairs of nodes along the communication links of the network. In this paper, we study gossiping using a linear‐cost model of communication which includes a start‐up time and a propagation time which is proportional to the amount of information transmitted. A minimum linear gossip graph is a graph (modeling a network), with the minimum possible number of links, in which gossiping can be completed in minimum time under the linear‐cost model. For networks with an even number of nodes, we prove that the structure of minimum linear gossip graphs is independent of the relative values of the start‐up and unit propagation times. We prove that this is not true when the number of nodes is odd. We present four infinite families of minimum linear gossip graphs. We also present minimum linear gossip graphs for all even numbers of nodes n ≤ 32 except n = 22. A linear (Δ, k)‐gossip graph is a graph with maximum degree Δ in which gossiping can be completed in k rounds with minimum propagation time. We present three infinite families of maximal linear (Δ, k)‐gossip graphs, that is, linear (Δ, k)‐gossip graphs with a maximum number of nodes. We show that not all minimum broadcast graphs are maximal linear (Δ, k)‐gossip graphs. © 2001 John Wiley & Sons, Inc.

A spanning subgraph $G'$ of a simple undirected graph G is a t-spanner of G if every pair of vertices that are adjacent in G are at distance at most t in $G'$. The parameter t is called the dilation of the spanner. Spanners with small dilations have many applications, such as their use as low-cost approximations of communication networks with only small degradations in performance. In this paper, we derive spanners with small dilations for four closely related bounded-degree approximations of hypercubes: butterflies, cube-connected cycles, binary de Bruijn graphs, and shuffle-exchange graphs. We give both direct constructions and methods for deriving spanners for one class of graphs from spanners for another class. We prove that most of our spanners are minimum in the sense that spanners with fewer edges have larger dilations.

In this paper we present three broadcast algorithms and lower bounds on the three main components of the broadcast time for 2-dimensional torus networks (wrap-around meshes) that use synchronous circuit-switched routing. The first algorithm is based on a recursive tiling of a torus and is optimal in terms of both phases and intermediate switch settings when the start-up time to initiate message transmissions is the dominant cost. It is the first broadcast algorithm to match the lower bound of log/sub 5/ N on number of phases (where N is the number of nodes). The second and third algorithms are hybrids which combine circuit-switching with the pipelining and arc-disjoint spanning trees techniques that are commonly used to speed up store-and-forward routing. When the propagation time of messages through the network is significant, our hybrid algorithms achieve close to optimal performance in terms of phases, intermediate switch settings, and total transmission time. They are the first algorithms to achieve this performance in terms of all three parameters simultaneously.

Abstract Broadcasting is an information dissemination problem in which information originating at one node of a communication network (modeled as a graph) must be transmitted to all other nodes as quickly as possible. A broadcast graph is a graph which permits broadcasting from any originator in minimum time. in this paper, we present new methods for constructing sparse broadcast graphs. Our constructions are based on graph compounding operations which are relative to vertex sets with certain properties that depend on the broadcast protocols of the graphs. We show that many previous methods for constructing sparse broadcast graphs are special cases of our methods. We demonstrate our constructions by producing new sparse broadcast graphs and by showing how many previously constructed graphs can be obtained in a systematic way.

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated methods to construct sparse graphs (networks) in which this process can be completed in minimum time from any originator. The graphs produced by these methods contain high degree vertices. [Liestman and Peters, SIAM Journal on Discrete Mathematics, 1 (1988), pp. 531–540 ] and [Bermond and Peyrat, Proceedings of the 19th SE Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 1988, pp. 283–292] began an investigation of graphs with fixed maximum degree in which broadcasting can be completed in near minimum time. This investigation is continued in this paper by giving lower bounds and constructing bounded degree graphs that allow rapid broadcasting. The constructions use ideas developed by Jerrum and Skyum [IEEE Transactions on Computers, C-33(2), 1984, pp. 190–194], which allow passing from a graph with good average case behaviour to one with good worst case behaviour. In addition, de Bruijn digraphs [de Bruijn, Koninkhjke Nederlandse Akademie Van Wetenschappen, Indagationes Mathematicae, Series A, 49 (1946), pp. 758–764], minimum broadcast graphs, and sparse broadcast graphs [Bermond, Hell, Liestman, and Peters, Discrete Applied Mathematics, to appear] are used. The resulting graphs yield the best broadcasting time known for bounded degree graphs. Also obtained are asymptotic upper and lower bounds for broadcasting time, as the maximum degree increases.

A smallest path between two points is a rectilinear path that simultaneously minimizes distance and the number of horizontal and vertical line segments in the path. Potential applications of smallest rectilinear paths include the simultaneous minimization of vias and wire lengths in two-layer chips, optimization of routes for robots, and the planning of traffic routes in cities with gridlike road systems. The existence of a smallest path between any pair of points in a simple rectilinear polygon with n boundary segments is proven and an optimal O(n) time sequential algorithm for finding the smallest paths is presented. An O(log n) parallel algorithm for an n processor CREW PRAM is described.>

Broadcasting is an information dissemination process in which a message is to be sent from a single originator to all members of a network by placing calls over the communication lines of the network. Several previous papers have investigated ways to construct sparse graphs (networks) in which this process can be completed in minimum time from any originator. The graphs produced by these methods contain high degree vertices. This paper describes graphs with fixed maximum degree in which broadcasting can be completed in near minimum time.

We adapt several parallel sorting algorithms (block sorting algorithms) and distributed sorting algorithms for implementation on an Ethernet network with diskless Sun workstations. We argue that the performance of sorting algorithms on local area networks (LANs) should be analyzed in a manner that is different from the ways that parallel and distributed sorting algorithms are usually analyzed. Consequently, we propose an empirical approach which will provide more insight into the performance of the algorithms. We obtain data on communication time, local processing time, and response time (i.e. total running time) of each algorithm for various file sizes and different numbers of processors. Comparing the performance data with our theoretical analysis, we attempt to provide rationale for the behaviour of the algorithms and project the future behaviour of the algorithms as file size, number of processors, or interprocessor communication facilities change.