Graph exploration is a theoretical model of the crucial task of moving an agent through an unknown environment. Here, an algorithm has to guide an explorer through a network with n vertices and m edges, visiting every vertex at least once. We consider the fixed-graph scenario by Kalyanasundaram and Pruhs (ICALP, 1993), where the explorer sees all vertices reachable in one step, their unique names and their distance from the current position. The algorithm only learns the structure of the graph during computation. Therefore, we are interested in the amount of crucial a-priori information (the advice complexity) needed to solve the problem optimally. We look at graph exploration on directed graphs and focus on cyclic solutions. It is known that O(nlog⁡n) bits of advice are necessary and sufficient to compute an optimal solution for general graphs. We present algorithms with O(m) advice, thus improving the bound for sparse graphs.

A dominating set S of a graph is a set of vertices such that each vertex is in S or has a neighbor in S. The goal of the dominating set problem is to find such a set of minimum cardinality. In the online setting, the graph is revealed vertex by vertex, together with edges to all previously revealed vertices. Advice complexity is a framework to measure the amount of information an online algorithm is lacking. Here, an online algorithm reads advice bits from an infinite binary tape prepared beforehand by an all-knowing oracle. The advice complexity is the total number of advice bits read during the computation. Besides giving some insight into what makes an online problem hard, advice complexity can also be used as a means for proving lower bounds on the competitive ratio achievable by randomized online algorithms. We analyze the advice complexity of the online dominating set problem. For general graphs, we show tight upper and lower bounds for optimality. Then, we use a result for c-competitiveness to prove that no randomized online algorithm can be better than n1−ε-competitive, for any ε>0. Finally, we analyze the advice complexity of various graph classes for optimality.

In the past memory allocation and communication between processors and memories in current MPSoC's, due to the small design space, was not a big challenge. Through advanced MPSoC's and improving techniques to interface Dynamic RAM (DRAM), allocation of logical data buffers to physical memories is no longer manageable manually. We present a heuristic for the mapping of logical data buffers to physical memories and the routing of data flows. Our heuristic use an approximation scheme to obtain an fractional solution, and randomized rounding. We evaluate our implementation for different values of e using representative data of the Long Term Evolution Standard.

The sizes of permutation networks and planar permutation networks for special sets of permutations are investigated. Several asymptotically optimal estimations for distinct subsets of the set of all permutations are established here. The two main results are as follows: A consequence of our results is the construction of a 4-degree network which can simulate each communication step of any hypercube algorithm using edges from at most a constant number of different dimensions in one communication step in $O(\log\log N)$ communication steps. An essential improvement of gossiping in vertex-disjoint path mode in bounded-degree networks follows.

The bandwidth problem has a long history and a number of important applications. It is the problem of enumerating the vertices of a given graph G such that the maximum difference between the numbers of adjacent vertices is minimal. We will show for any constant k/spl epsiv/N that there is no polynomial time approximation algorithm with an approximation factor of k. Furthermore, we will show that this result holds also for caterpillars, a class of restricted trees. We construct for any x,/spl epsiv//spl isin/R with x>1 and /spl epsiv/>0 a graph class for which an approximation algorithm with an approximation factor of x+/spl epsiv/ exists, but the approximation of the bandwidth problem within a factor of x-/spl epsiv/ is NP-complete. The best previously known approximation factors for the intractability of the bandwidth approximation problem were 1.5 for general graphs and 4/3 for trees.

We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline.We show that the problem of transmitting optimally many messages is NP-hard, both when messages may be buffered in transit and when they may not be; for either case, we present efficient algorithms that produce approximately optimal schedules.In particular, our bufferless scheduling algorithm achieves throughput that is within a factor of two of optimal.We show that buffering can improve throughput in general by a logarithmic factor (but no more), but that in several significant special cases, such as when all messages can be released immediately, buffering can help by only a small constant factor.Finally, we show how to convert our centralized, offline bufferless schedules to equally productive fully