We present the Cost-Distance problem: finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known $O(\log k)$ randomized approximation scheme for Cost-Distance, where k is the number of sources. We reduce several common network design problems to Cost-Distance, obtaining (in some cases) the first known logarithmic approximation for them. These problems include single-sink buy-at-bulk with variable pipe types between different sets of nodes, facility location with buy-at-bulk–type costs on edges (integrated logistics), constructing single-source multicast trees with good cost and delay properties, priority Steiner trees, and multilevel facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems.

This article relates the notion of fairness in online routing and load balancing to vector majorization as developed by Hardy et al. [1929]. We define α -supermajorization as an approximate form of vector majorization, and show that this definition generalizes and strengthens the prefix measure proposed by Kleinberg et al. [2001] as well as the popular notion of max-min fairness .The article revisits the problem of online load-balancing for unrelated 1-∞ machines from the viewpoint of fairness. We prove that a greedy approach is O (log n )-supermajorized by all other allocations, where n is the number of jobs. This means the greedy approach is globally O (log n )- fair . This may be contrasted with polynomial lower bounds presented by Goel et al. [2001] for fair online routing.We also define a machine-centric view of fairness using the related concept of submajorization . We prove that the greedy online algorithm is globally O (log m )- balanced , where m is the number of machines.

Wireless sensor networks (WSNs) are emerging as an effective means for environment monitoring. This paper investigates a strategy for energy efficient monitoring in WSNs that partitions the sensors into covers, and then activates the covers iteratively in a round-robin fashion. This approach takes advantage of the overlap created when many sensors monitor a single area. Our work builds upon previous work in [13], where the model is first formulated. We have designed three approximation algorithms for a variation of the SET K-COVER problem, where the objective is to partition the sensors into covers such that the number of covers that include an area, summed over all areas, is maximized. The first algorithm is randomized and partitions the sensors, in expectation, within a fraction 1-1 e (~.63) of the optimum. We present two other deterministic approximation algorithms. One is a distributed greedy algorithm with a 1 2 approximation ratio and the other is a centralized greedy algorithm with a 1-1 e approximation ratio. We show that it is NP-Complete to guarantee better than 15 16 of the optimal coverage, indicating that all three algorithms perform well with respect to the best approximation algorithm possible in polynomial time, assuming P ≠ NP. Simulations indicate that in practice, the deterministic algorithms perform far above their worst case bounds, consistently covering more than 72% of what is covered by an optimum solution. Simulations also indicate that the increase in longevity is proportional to the amount of overlap amongst the sensors. The algorithms are fast, easy to use, and according to simulations, significantly increase the longevity of sensor networks. The randomized algorithm in particular seems quite practical.

We consider the problem of incrementally designing a network to route demand to a single sink on an underlying metric space. We are given cables whose costs per unit length scale in a concave fashion with capacity. Under certain natural restrictions on the costs (called the Access Network Design constraints), we present a simple and efficient randomized algorithm that is competitive to the minimum cost solution when the demand points arrive online. In particular, if the order of arrival is a random permutation, we can prove a O(1) competitive ratio. For the fully adversarial case, the algorithm is O(K) -competitive, where K is the number of different pipe types. Since the value of K is typically small, this improves the previous O(log n log log n)-competitive algorithm which was based on probabilistically approximating the underlying metric by a tree metric. Our algorithm also improves the best known approximation ratio and running time for the offline version of this problem.

Presents the cost-distance problem, which consists of finding a Steiner tree which optimizes the sum of edge costs along one metric and the sum of source-sink distances along an unrelated second metric. We give the first known O(log k) randomized approximation scheme for the cost-distance problem, where k is the number of sources. We reduce several common network design problems to cost-distance problems, obtaining (in some cases) the first known logarithmic approximation for them. These problems include a single-sink buy-at-bulk problem with variable pipe types between different sets of nodes, facility location with buy-at-bulk-type costs on edges, constructing single-source multicast trees with good cost and delay properties, and multi-level facility location. Our algorithm is also easier to implement and significantly faster than previously known algorithms for buy-at-bulk design problems.

This paper presents online algorithms for routing and bandwidth allocation which simultaneously approximate fair and max-throughput solutions.In fact, the algorithms solve a more difficult problem: for any bandwidth b, the number of sessions that get bandwidth b in the online algorithm is not smaller than the number of sessions receiving vb offiine, where V is the competitive ratio.This problem is provably harder than the problem of maximizing throughput (e.g.[4]) or the problem of maximizing the bandwidth assigned to the most starved session (e.g.[3]).For the case where the algorithm assigns bandwidths, we present an O(log 2 n log 1+~ U/e)-competitive algorithm, for any e, where U is the minimum (over all choices of routes) of the 'maximum number of sessions routed along any single link.We also show an ~(log 1+~ U/e) lower bound in this model.For a more practically interesting model where the algorithm assigns routes and weights, and where these weights are used to drive the Weighted Fair Queuing policy in the routers, we present an O(log2nlogU)competitive algorithm.We also show that the dependence on U is necessary by presenting an ~(~) lower bound. The upper and lower bounds presented in [4] for online maximization of throughput become invalid if we

In this paper we consider the online ftp problem.The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network.The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as mu-stretch, total flow time, max flow time, and total completion time.In particular, we show how to achieve optimum total flow time and optimum max.stretch if we increase the capacity of the underlying network by a logarithmic factor.We show that the resource augmentation is necessary by proving polynomial lower bounds on the maxstretch and total flow time for the case where online and offline algorithms are using same-capacity edges.Moreover, we also give poly-logarithmic lower bounds on the resource augmentation factor necessary in order to keep the total Aow time and max.stretch within a constant factor of optimum.

A snapshot scan algorithm produces an "instantaneous" picture of a region of shared memory that may be updated by concurrent processes. Many complex shared memory algorithms can be greatly simplified by structuring them around the snapshot scan abstraction. Unfortunately, the substantial decrease in conceptual complexity quite often is counterbalanced by an increase in computational complexity. In this paper, we introduce the notion of a weak snapshot scan, a slightly weaker primitive that has a more efficient implementation. We propose the following methodology for using this abstraction: first, design and verify an algorithm using the more powerful snapshot scan; second, replace the more powerful but less efficient snapshot with the weaker but more efficient snapshot, and show that the weaker abstraction nevertheless suffices to ensure the correctness of the enclosing algorithm. We give two examples of algorithms whose performance is enhanced while retaining a simple modular structure: bounded concurrent timestamping and bounded randomized consensus. The resulting timestamping protocol dominates all other currently known timestamping protocols: it matches the speed of the fastest known bounded concurrent timestamping protocol while actually reducing the register size by a logarithmic factor. The resulting randomized consensus protocol matches the computational complexity of the best known protocol that uses only bounded values.

Y. Bartal (1996, 1998) gave a randomized polynomial time algorithm that given any n point metric G, constructs a tree T such that the expected stretch (distortion) of any edge is at most O (log n log log n). His result has found several applications and in particular has resulted in approximation algorithms for many graph optimization problems. However approximation algorithms based on his result are inherently randomized. In this paper we derandomize the use of Bartal's algorithm in the design of approximation algorithms. We give an efficient polynomial time algorithm that given a finite n point metric G, constructs O(n log n) trees and a probability distribution /spl mu/ on them such that the expected stretch of any edge of G in a tree chosen according to /spl mu/ is at most O(log n log log n). Our result establishes that finite metrics can be probabilistically approximated by a small number of tree metrics. We obtain the first deterministic approximation algorithms for buy-at-bulk network design and vehicle routing; in addition we subsume results from our earlier work on derandomization. Our main result is obtained by a novel view of probabilistic approximation of metric spaces as a deterministic optimization problem via linear programming.

Suppose there are n servers and a sequence of tasks, each of which arrives in an on-line fashion and can be handled by a subset of the servers. The level of the service required by a task is known upon arrival, but the duration of the service is unknown. The on-line load balancing problem introduced by Azar, Broder, and Karlin is to assign each task to an appropriate server so that the maximum load on the servers is minimized. Azar, Broder, and Karlin proved a lower bound of Ω(n12) on the competitive ratio for this problem. However, their lower bound argument used a sequence of tasks with exponential duration, and therefore this did not preclude a possible competitive ratio of the form poly(log T) where T denotes an upper bound on the duration of each task. In this paper, we prove a lower bound of Ω(min{n14, T13}), thereby proving that a poly(log T) competitive ratio is not possible. This should be compared to the analogous case for known-duration tasks, where it is possible to achieve O(log nT)-competitive ratio.

In this paper we study the problem of on-line allocation of routes to virtual circuits (both point-to-point and multicast ) where the goal is to route all requests while minimizing the required bandwidth. We concentrate on the case of Permanent virtual circuits (i.e., once a circuit is established it exists forever), and describe an algorithm that achieves on O (log n ) competitive ratio with respect to maximum congestin, where n is the number of nodes in the network. Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O (log n ) factor. We also show that this result is tight, that is, for any on-line algorithm there exists a scenario in which Ω(log n ) increase in bandwidth is necessary in directed networks. We view virtual circuit routing as a generalization of an on-line load balancing problem, defined as follows: jobs arrive on line and each job must be assigned to one of the machines immediately upon arrival. Assigning a job to a machine increases the machine's load by an amount that depends both on the job and on the machine. The goal is to minimize the maximum load. For the related machines case, we describe the first algorithm that achieves constant competitive ratio. for the unrelated case (with n machines), we describe a new method that yields O (log n )-competitive algorithm. This stands in contrast to the natural greed approach, whose competitive ratio is exactly n .

This paper introduces a new distributed data object called Resource Controller that provides an abstraction for managing the consumption of a global resource in a distributed system. Examples of resources that may be managed by such an object include; number of messages sent, number of nodes participating in the protocol, and total CPU time consumed. The Resource Controller object is accessed through a procedure that can be invoked at any node in the network. Before consuming a unit of resource at some node, the controlled algorithm should invoke the procedure at this node, requesting a permit or a rejection. The key characteristics of the Resource Controller object are the constraints that it imposes on the global resource consumption. An (M, W)-Controller guarantees that the total number of permits granted is at mostM; it also ensures that, if a request is rejected, then at leastM—Wpermits are eventually granted, even if no more requests are made after the rejected one. In this paper, we describe several message and space-efficient implementations of the Resource Controller object. In particular, we present an (M, W)-Controller whose message complexity isO(nlog2nlog(M/(W+ 1)) wherenis the total number of nodes. This is in contrast to theO(nM)message complexity of a fully centralized controller which maintains a global counter of the number of granted permits at some distinguished node and relays all the requests to the node.

Minimumcost multicommodity flow is an instance of a simpler problem (multicommodity flow)to which a cost constraint has been added.In this paper we present a general scheme for solving a large class of such "cost-added" problems-even if more than one cost is added.One of the main applications of this method is a new deterministic algorithm for approximately solving the minimumcost multicommodity flow problem.techniques in [15] and a generalization of the round-robin approach of [16] to multicommodity flow without costs.

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming. The best of these algorithms uses a fast matrix multiplication algorithm and takes O(k3.5n3m0.5 log(nDU)) time for the multicommodity flow problem with integer demands and at least O(k2.5n2m0.5 log(nϵ−1DU)) time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity. As a consequence, even multicommodity flow problems with just a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems. In this paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem. The running time of our randomized algorithm is (up to log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation. In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2n) single-commodity minimum-cost flow problems. Our k-commodity algorithm runs in O (knm log4n) time with high probability. We also describe a deterministic algorithm that uses an O(k)-factor more time. Given any multicommodity flow problem as input, both algorithms are guaranteed to provide a feasible solution to a modified flow problem in which all capacities are increased by a (1 + ϵ)-factor, or to provide a proof that there is no feasible solution to the original problem. We also describe faster approximation algorithms for multicommodity flow problems with a special structure, such as those that arise in "sparsest cut" problems and uniform concurrent flow problems.

Classical routing and admission control strategies achieve provably good performance by relying on an assumption that the virtual circuits arrival pattern can be described by some a priori known probabilistic model. A new on-line routing framework, based on the notion of competitive analysis, was proposed. This framework is geared toward design of strategies that have provably good performance even in the case where there are no statistical assumptions on the arrival pattern and parameters of the virtual circuits. The on-line strategies motivated by this framework are quite different from the min-hop and reservation-based strategies. This paper surveys the on-line routing framework, the proposed routing and admission control strategies, and discusses some of the implementation issues.>

This paper describes new algorithms for approximately solving the concurrent multicommodity flow problem with uniform capacities. These algorithms are much faster than algorithms discovered previously. Besides being an important problem in its own right, the uniform-capacity concurrent flow problem has many interesting applications. Leighton and Rao used uniform-capacity concurrent flow to find an approximately “sparsest cut” in a graph and thereby approximately solve a wide variety of graph problems, including minimum feedback arc set, minimum cut linear arrangement, and minimum area layout. However, their method appeared to be impractical as it required solving a large linear program. This paper shows that their method might be practical by giving an $O(m^2 \log m)$ expected-time randomized algorithm for their concurrent flow problem on an m-edge graph. Raghavan and Thompson used uniform-capacity concurrent flow to solve approximately a channel width minimization problem in very large scale integration. An $O(k^{{3 / 2}} (m + n\log n)$ expected-time randomized algorithm and an $O(k\min \{ n,k\} (m + n\log n)\log k)$ deterministic algorithm is given for this problem when the channel width is $\Omega (\log n)$, where k denotes the number of wires to be routed in an n-node, m-edge network.

This paper describes a deterministic algorithm for reconfiguring a multibutterfly network with faulty switches. Unlike previous reconfiguration algorithms, the algorithm is performed entirely by the network, without the aid of any off-line computation, even though many of the switches may be faulty. The algorithm reconfigures an N-input multibutterfly network in O(logN) time. After reconfiguration, the multibutterfly can tolerate f worst-case faults and still route any permutation between some set of N/spl minus/O(f) inputs and N/spl minus/O(f) outputs in O(log N) time.>

We develop a framework that allows us to address the issues of admission control and routing in high-speed networks under the restriction that once a call is admitted and routed, it has to proceed to completion and no reroutings are allowed. The "no rerouting" restriction appears in all the proposals for future high-speed networks and stems from current hardware limitations, in particular the fact that the bandwidth-delay product of the newly developed optical communication links far exceeds the buffer capacity of the network. In case the goal is to maximize the throughput, our framework yields an on-line O(log nT)-competitive strategy, where n is the number of nodes in the network and T is the maximum call duration. In other words, our strategy results in throughput that is within O(log nT) factor of the highest possible throughput achievable by an omniscient algorithm that knows all of the requests in advance. Moreover, we show that no on-line strategy can achieve a better competitive ratio. Our framework leads to competitive strategies applicable in several more general settings. Extensions include assigning each connection an associated "profit" that represents the importance of this connection, and addressing the issue of call-establishment costs.>

In this paper we study an idealized problem of on-line allocation of routes to virtual circuits where the goal is to minimize the required bandwidth.For the case where virtual circuits continue to exist forever, we describe an algorithm that achieves an O (log n) competitive ratio, where n is the number of nodes in the network.Informally, our results show that instead of knowing all of the future requests, it is sufficient to increase the bandwidth of the communication links by an O(log n) factor.We also show that this result is tight, i.e. for any on-line algorithm there exists a scenario in which O(log n) increase in bandwidth is necessary.We view virtual circuit routing as a generalization of an on-line scheduling problem, and hence a major part of the paper focuses on development of algorithms for non-preemptive on-line scheduling for related and unrelated machines.Specialization of routing to scheduling leads us to concentrate on scheduling in the case where jobs must be assigned immediately upon arrival; assigning a job to a machine increases this machine's load by an amount that depends both on the job and on the machine.The goal is to minimize the maximum load.For the related machines case, we describe the first algorithm that achieves constant competitive ratio.For the unrekzted case (with n machines), we describe a new method that yields O(log n)-competitive algorithm.This stands in contrast to the natural greedy approach, which we show has only a ~(n) competitive ratio.The virtual circuit routing result follows as a generalization of the unrelated machines case.

In this paper we show that, given a graph and parameters 6 and r, we can find either a K,,.minor or an edge-cut of size O(mT/6) whose removal yields components of weak diameter O(T-26); i.e., every pair of nodes in such a component are at distance 0(r26) in the original graph.Using this lemma, we improve the best known bounds for the rein-cut max-flow ratio for mukicommodity flows in graphs with forbidden small minors.In general graphs, it was known that the ratio is O(log k) for the uniform-demand case (the case where there is a unit-demand commodity between every pair of nodes), and that the ratio is 0(log2 k) for arbitrary demands, where k is the number of commodities.In this paper we show that for graphs excluding any fixed graph as a minor (e.g.planar graphs or boundedgenus graphs), the ratio is O(1) for the uniform-demand case and O(log k) for the arbitrary demand case.For such graphs, our method yields rein-ratio cut approximation algorithms with performance bounds that match the above ratios.Computation of such cuts is a basic step for a variety of approximation algorithms for NP-complete problems.

In this paper we consider the worst case ratio between the capaciry of minimum-cuts and the value of maximum-flow for multicommodity flow problems.We improve the best known bounds for the rein-cut rnax-flow ratio for multicommodi~flows in undirected graphs, by replacing the O(log D) in the bound by O(log k), where D denotes the sum of all demands, and k denotes the number of commodities.In essence we prove that up to constant factors the worst tin-cut max-flow ratios appear in problems where demands are integral and polynomial in the number of commodities.Klein, Rae, Agrawal, and Ravi have previously proved that if the demands and the capacities are integral, then the rein-cut max-flow ratio in general undirected graphs is bounded by O(log C log D), where C denotes the sum of all the capacities.Tragoudas has improved this bound to O(log n log D),where n is the number of nodes in the network.Garg, Vazirani and Yannakakis further improved this to O(log k log D).Klein, Plotkin and Rao have proved that for planar networks, the ratio is O(log D).Our result improves the bound for general nemvorks to O(log2 k) and the bound for planar networks to O(log k).In both cases our result implies the first non-trivial bound that is independent of the magnitude of the numbers involved.The method presented in this paper can be used to give polynomial time approfi~~on ~gorithms tO the ~~mum-cuts in the network UP to the above factors.Compumtion Of such cuts is a basic step for a varie~of approximation algorithms for NP-complete problems.

In this paper interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. This algorithm finds a maximum cardinality matching in a bipartite graph with n nodes and m edges in $O(\sqrt m \log ^3 n)$ time on a CRCW PRAM. The results here extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding $O(\sqrt m \log ^2 n\log nC)$ algorithms, where $C > 1$ is an upper bound on the absolute value of the integral weights or costs in the two problems, respectively. The results here improve previous bounds on these problems and introduce interior-point methods to the context of parallel algorithm design.

Fast algorithms that find approximate solutions for a general class of problems, which are called fractional packing and covering problems, are presented. The only previously known algorithms for solving these problems are based on general linear programming techniques. The techniques developed greatly outperform the general methods in many applications, and are extensions of a method previously applied to find approximate solutions to multicommodity flow problems. The algorithms are based on a Lagrangian relaxation technique, and an important result is a theoretical analysis of the running time of a Lagrangian relaxation based algorithm. Several applications of the algorithms are presented.>

All previously known algorithms for solving the multicommodity flow problem with capacities are based on linear programming.The best of these algorithms [14] uses a fast matrix multiplication algorithm and takes O(k25n2m5 log(nDU))time to find an approximate solution, where k is the number of commodities, n and m denote the number of nodes and edges in the network, D is the largest demand, and U is the largest edge capacity.Substantially more time is needed to find an exact solution.As a consequence, even multicommodit y flow problems with jnst a few commodities are believed to be much harder than single-commodity maximum-flow or minimum-cost flow problems.In thk paper, we describe the first polynomial-time combinatorial algorithms for approximately solving the multicommodity flow problem.The running time of our randomized algorithm is (up to ,log factors) the same as the time needed to solve k single-commodity flow problems, thus giving the surprising result that approximately computing a k-commodity maximum-flow is not much harder than computing about k single-commodity maximum-flows in isolation.In fact, we prove that a (simple) k-commodity flow problem can be approximately solved by approximately solving O(k log2 n) single-commodity minimum-cost flow problems.Our k-commodity algorithm runs in O(knm log4 n) time with high probability.We also describe a deterministic algorithm that uses an O(k)-factor more time.Given any multicommodit y flow problem as input, both rdgorithms are guaranteed to provide a feasible solution to a modified @ 1991

The authors introduce a concept of network decomposition, a partitioning of an arbitrary graph into small-diameter connected components, such that the graph created by contracting each component into a single node has low chromatic number. They present an efficient distributed algorithm for constructing such a decomposition and demonstrate its use for design of efficient distributed algorithms. The method yields new deterministic distributed algorithms for finding a maximal independent set in an arbitrary graph and for ( Delta +1)-coloring of graphs with maximum degree Delta . These algorithms run in O(n/sup epsilon /) time for epsilon =O((log log n/log n)/sup 1/2/), whereas the best previously known deterministic algorithms required Omega (n) time. The techniques can also be used to remove randomness from the previously known most distributed breadth-first search algorithm.>

Interior-point methods for linear programming, developed in the context of sequential computation, are used to obtain a parallel algorithm for the bipartite matching problem. The algorithm runs in O*( square root m) time. The results extend to the weighted bipartite matching problem and to the zero-one minimum-cost flow problem, yielding O*( square root m log C) algorithms. This improves previous bounds on these problems and illustrates the importance of interior-point methods in parallel algorithm design.>

A generalization of the maximum-flow problem is considered in which the amounts of flow entering and leaving an arc are linearly related. More precisely, if x(e) units of flow enter an arc e, x(e) lambda (e) units arrive at the other end. For instance, nodes of the graph can correspond to different currencies, with the multipliers being the exchange rates. Conservation of flow is required at every node except a given source node. The goal is to maximize the amount of flow excess at the source. This problem is a special case of linear programming, and therefore can be solved in polynomial time. The authors present polynomial-time combinatorial algorithms for this problem. The algorithms are simple and intuitive.>

The authors present the first sub-linear-time deterministic parallel algorithms for bipartite matching and several related problems, including maximal node-disjoint paths, depth-first search, and flows in zero-one networks. The results are based on a better understanding of the combinatorial structure of the above problems, which lead to new algorithmic techniques. In particular, it is shown how to use maximal matching to extend, in parallel, a current set of node-disjoint paths and how to take advantage of the parallelism that arises when a large number of nodes are active during an execution of a push/relabel network flow algorithm. It is also shown how to apply the techniques to design parallel algorithms for the weighted versions of the above problems.>

This paper describes efficient deterministic techniques for breaking symmetry in parallel. These techniques work well on rooted trees and graphs of constant degree or genus. The primary technique allows us to 3-color a rooted tree in $O( \lg^* n )$ time on an EREW PRAM using a linear number of processors. These techniques are used to construct fast linear processor algorithms for several problems, including the problem of $( \Delta + 1)$-coloring constant-degree graphs and 5-coloring planar graphs. Lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs are also proved.

We introduce a new primitive, the Resource Controller, which abstracts the problem of controlling the total amount of resources consumed by a distributed algorithm. We present an efficient distributed algorithm to implement this abstraction. The message complexity of our algorithm per participating node is polylogarithmic in the size of the network, compared to the linear cost per node of the naive algorithm. The implementation of our algorithm is simple and practical and the techniques used are interesting because a global quantity is managed in a distributed way. The Resource Controller can be used to construct efficient algorithms for a number of important problems, such as the problem of bounding the worst-case message complexity of a protocol and the problem of dynamically assigning unique names to nodes participating in a protocol.

We describe efficient deterministic techniques for breaking symmetry in parallel. The techniques work well on rooted trees and graphs of constant degree or genus. Our primary technique allows us to 3-color a rooted tree in Ο(lg*n) time on an EREW PRAM using a linear number of processors. We apply these techniques to construct fast linear processor algorithms for several problems, including (Δ + 1)-coloring constant-degree graphs, 5-coloring planar graphs, and finding depth-first-search trees in planar graphs. We also prove lower bounds for 2-coloring directed lists and for finding maximal independent sets in arbitrary graphs.