A λ-coloring of a graph G is an assignment of colors from the integer set {0,…,λ} to the vertices of the graph G such that vertices at distance of at most two get different colors and adjacent vertices get colors which are at least two apart. The problem of finding λ-colorings with optimal or near-optimal λ arises in the context of radio frequency assignment. We show that the problem of finding the minimum λ for planar graphs, bipartite graphs, chordal graphs and split graphs is NP-complete. We also give approximation algorithms for λ-coloring and compute upper bounds on the best possible λ for outerplanar graphs, graphs of treewidth k, permutation and split graphs. Except in the case of split graphs, all the above bounds for λ are linear in Δ, the maximum degree of the graph. For split graphs, we give a bound of ½Δ1.5 + 2Δ and we show that there are split graphs G with λ(G) = Ω(Δ1.5). Similar results are also given for variations of the λ-coloring problem.

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1<i<(/spl sigma/-1), where d(u, v) is the distance (i.e., the minimum number of edges) between the vertices u and v. An optimal L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring for G is one using the smallest range /spl lambda/ of integers over all such colorings. This problem has relevant application in channel assignment for interference avoidance in wireless networks, where channels (i.e., colors) assigned to interfering stations (i.e., vertices) at distance i must be at least /spl delta//sub i/ apart, while the same channel can be reused in vertices whose distance is at least /spl sigma/. In particular, two versions of the coloring problem - L(2, 1, 1) and L(/spl delta//sub 1/, 1,..., 1) - are considered. Since these versions of the problem are NP-hard for general graphs, efficient algorithms for finding optimal colorings are provided for specific graphs modeling realistic wireless networks, including rings, bidimensional grids, and cellular grids.

Abstract We give complete characterizations for the classes of graphs with uniform cost links that admit optimum all shortest paths 1‐SLIRS (strict linear interval routing schemes) and 1‐LIRS (linear interval routing schemes). The characterization of all the interval routing schemes with uniform cost links that represent only a single shortest path is known to be NP‐complete. For any integer k > 0, we also show that the class of graphs with dynamic cost links that admit optimum all shortest paths k‐IRS (SIRS, LIRS, SLIRS) is equivalent to the class of graphs with dynamic cost links that admit an optimum single shortest path k‐IRS (SIRS, LIRS, SLIRS) and also equivalent to the class of graphs with dynamic cost links that admit single paths up to any constant stretch factor k‐IRS (SIRS, LIRS, SLIRS). © 2001 John Wiley & Sons, Inc.

No abstract available.

In this work we propose simple and efficient protocols for counting and leader election in mobile networks.For mobile networks with fixed base stations we provide a new and very efficient protocol for counting the number of mobile hosts.The main part of the work concentrates on ad-hoc networks (no fixed subnetwork).We provide a model for these networks and leader election (and a special form of counting) protocols for both named and anonymous mobile hosts.In this work we define two protocol classes, the Non-Compulsoryprotocols, which do not affect the motion of the hosts and the Compulsory, which determine the motion of some or all the hosts.By assuming that the mobile hosts move as if each one is doing a continuous random walk on their allowable space S of motions, and by assuming a universal time, we show that our leader election protocol terminates (with high probability and also on the average) in time asymptotically linear to the size of the space S, measured as its volume divided by the volume of the sphere defined by the range of transmission of each mobile host.We also provide a simple but very efficient Compulsory (forced random walks) Las Vegas protocol for leader election in ad-hoc networks, which also allows counting, with termination detection.Our analysis techniques for the meeting time of concurrent random walks extend the known facts and are tight.They may be used as an analysis tool in the design of many other distributed protocols.This is the first algorithmic and characterization work, to our knowledge, for ad-hoc networks.

An interval routing scheme is a general method of routing messages in a distributive network using compact routing tables. In this paper, concepts related to optimal interval routing schemes are introduced and explored. Several problems concerning the insertion of nodes and joining of separate networks by a new link to form larger ones are considered. Various applications to distributed computing are given. In particular, leader-finding and generation of spanning trees in arbitrary networks are shown to require at most O(N+E) messages when a suitable interval routing scheme is available.