Tracking Users in Cellular Networks using Timing Information^{∗}

E. Kranakis

Carleton University, Canada

D. Krizanc

Wesleyan University, USA

S. Shende

Rutgers University, USA

Abstract

We consider the problem of tracking a user moving through a cellular network using node queries that provide information as to last time the user visited the node. Queries are executed in rounds, each round may involve queries to many nodes simultaneously, and the user may move at the same time that queries are performed. The cost measures considered are the number of rounds required to find the user and the total number of queries made during the execution of the algorithm. We present a number of algorithms for general networks, as well as upper and lower bounds for specific network topologies.

Keywords cellular networks, timing information, tracking

1 Introduction

The problem of tracking users in cellular networks has been well-studied [1, 2, 5, 12, 13, 8, 14, 15]. For the most part, the solutions involve some compromise between maintaining a central database of the precise location of all users at any time or querying the nodes of the network whenever a user’s location must be determined. The algorithms that query the network assume that nodes provide only one bit of information, i.e., the presence or non-presence of the user at the location queried. In such a model, if no further information is provided, any algorithm that finds a user with certainty must eventually query all of the nodes that could conceivably contain the user. In this paper, we assume that the nodes maintain a list of users that they have serviced recently and when queried respond with the time that a user last visited the node. Under this assumption, we show query algorithms for user tracking which significantly improve upon search strategies that use only the standard single bit response. Note that we do not assume that other information concerning a user’s behavior is available (e.g., the probability of being at a particular node) but such information could be combined with our techniques to get even better results.

∗Research of the first author was supported in part by NSERC (Natural Sciences and Engineering Research Council of Canada) and MITACS (Mathematics of Information Technology and Complex Systems) grants. The third author acknowledges research support in part from NSF (National Science Foundation) grant No. 99-03420.

1.1 The Model

A cellular network is modeled by a synchronous network G = (V,E): V is the set of cells or nodes, and E the set of adjacencies between nodes. Let n = |V |, m = |E| and d the maximum degree of any node. Originally (i.e., at time 0), the user occupies a certain node s, known to a central query algorithm. (This could be, for instance, the node at which the user was last found during a search operation.) At each time unit the user may either stay at its current node or move to an adjacent node. At a later time t, a search algorithm begins searching for the mobile by querying nodes of the network. The search algorithm has access to the whole network and can query any number of nodes at the same time. The algorithm succeeds when it queries the node that contains the user. The network is synchronous: this means that the queries are executed simultaneously and the user, the nodes and the search algorithm use identical clocks. Our complexity measures are (1) the number of rounds r taken by the search algorithm to find the user and (2) the total number of queries q used in all rounds.

An important point about the model is that the search algorithm may query any node of the graph, while, at the same time, the user is moving along vertices of the graph. In particular when, at a given time instance, the search algorithm has determined that the position of the user is a certain node u, at the next time step the search algorithm must query not only the node u but also all its neighbors in order to locate the user with certainty.

A query to a node is of the form: “When did the user last visit this node?” The answer to the query is an integer k indicating that the user last visited the node k time units ago. If the user has never visited the node this is indicated by some special value, e.g., k = −1. A number of variations on this model are possible. If the node only returns 0 to indicate the user is not present or 1 to indicate the user is present we get the model most often studied in the literature. Models in between these two might be one in which the node is able to remember a user’s last visit for limited amount of time or for a limited number of users that are not present. A model stronger than the one considered here might include information of the form, the time the user was last seen as well as the cell the user went to upon leaving. Note that for constant degree networks, this model would be equivalent to the one considered here as one could always query a node and all of its neighbors with only constant overhead. We will consider the first model above and we refer to it as the standard timed model.

1.2 Contributions of the paper

We study the problem of designing search algorithms that minimize both the number of rounds required to find the user and the total number of queries used over all rounds. We present three upper bounds that work on arbitrary topologies. The efficiency of the first depends only on the degree of the graph, the second uses separator properties of the graph and the third depends on the cutwidth of the graph. These upper bounds can be adapted to get improved results for specific topologies. We consider lines, trees, meshes and cliques, as well as arbitrary planar topologies. Finally we give lower bounds which show some of the upper bounds are tight for specific cases.

2 Upper Bounds

In this section we present a variety of algorithms that provide upper bounds for arbitrary graphs, planar graphs, meshes, trees, and lines.

2.1 Arbitrary graphs

We present three algorithms that work on arbitrary topologies. The efficiency of the first is limited by the maximum degree d of the underlying network.

Theorem 1 Suppose that a user begins moving at time 0 from a known location s of an arbitrary connected graph. There is a search algorithm starting at time t that will find the user in at most r rounds with a total of at most O(rd^{⌈t/r⌉+1}) queries.

Proof (Theorem 1). Beginning with the start node s, in each round the search algorithm queries all the nodes in a neighborhood N_{⌈t/r⌉+1}(u) of nodes at distance at most ⌈t/r⌉ from a given node u. Initially, u := s. The node is updated with that node in N_{⌈t/r⌉+1}(u) that has seen the user most recently. At the end of the ith round the user will move to a neighbor of a previously occupied node during the i − 1 round, while the search algorithm is at a distance of at most t − i⌈t/r⌉ from the user. So in r rounds the search algorithm will be at a distance of at most t − r⌈t/r⌉ ≤ 0 from the user. So the user will be located after r rounds. This completes the proof of Theorem 1. □

Our second algorithm depends on the separator properties of a graph. An edge separator of graph G is a set S of edges of the graph that separates the graph into two or more parts of at most n/2 nodes each. We define the edge separator function of the graph G as follows: for any integer k,

F_{G}(k) = max (induced subgraph G_{k})  min (S edge separator of G_{k})|S|,  (1)

where the maxis taken over all induced subgraphs G_{k} of G with at most k nodes, and the minover all edge separators S of G_{k}. We prove the following theorem.

Theorem 2 Suppose that a user begins moving at time 0 from a known location s of an arbitrary connected graph. There is an algorithm that will find the user in at most O(logn) rounds with a total of at most

2 ∑_{i=0}^{⌈logn⌉}∑_{j=0}^{i} F_{G}(n/2^{j})

queries, where F_{G} is the edge separator function of the graph G.

Proof (Theorem 2). Let the graph be G = (V,E). In the first round we consider an edge separator with node set S_{1} of the graph G of size at most 2F_{G}(n) (i.e, at most 2 nodes per edge in the separator). The search algorithm queries the nodes in S_{1} and determines in which component of the graph minus the separator the user lies. In the next round the search algorithm queries the set of nodes in S_{2}, where S_{2} is the set of nodes in an edge separator of the component previously determined, along with the nodes of S_{1} (since, in the meantime, the user may have escaped to a node belonging to S_{1}). We iterate this process and we observe that if S_{i} is the new set of nodes queried in the i-the round then the number of queries in the i-th round is at most |S_{1}| + |S_{2}| + ··· + |S_{i}|. This implies that the total number of queries in all rounds is at most

∑_{i=0}^{⌈logn⌉}∑_{j=0}^{i} |S_{j}|.

The upper bound stated in the theorem now follows easily from the definition (see Equation 1) of the edge separator function of the graph. This completes the proof of Theorem 2. □

The cutwidth of a graph G, denoted by c(G), is the smallest integer k such that the n vertices of the graph can be arranged in a linear order v_{1},v_{2},...,v_{n} in such a way that for all i < n there are at most k edges with one endpoint in v_{1},...,v_{i} and the other in v_{i+1} ,...,v_{n}.

Theorem 3 Suppose that a user begins moving at time 0 from a known location s of an arbitrary connected graph. There is an algorithm that will find the user in at most O(logn) rounds with a total of at most O(c(G)logn) queries, where c(G) is the cutwidth of the graph G.

Proof (Theorem 3). Let the cutwidth of the graph G be c := c(G). Therefore there is a linear order v_{1},v_{2},...,v_{n} of the vertices of the graph such that for all i < n there are at most c edges with one endpoint in v_{1},...,v_{i} and the other in v_{i+1} ,...,v_{n}. At any round of the algorithm, we maintain an interval v_{a} to v_{b} in which we are certain the user lies. Initially, v_{a} = v_{1} and v_{b} = v_{n}. For such an order of the vertices define the sets A = {v_{a},...,v_{⌊(a+b)/2⌋}},B = {v_{⌊(a+b)/2⌋+1} ,...,v_{b}}.

The search algorithm queries the set S of nodes consisting of the endpoints of edges between (i) v_{1},...,v_{a−1} and v_{a},...,v_{b}, (ii) v_{a},...,v_{b} and v_{b+1} ,...,v_{n} and (iii) A and B, plus the node s. Note that this consists of at most 6c+1 nodes. If the user is among these nodes then we are done. Else, let u ∈ S be the node queried by the search algorithm that saw the user last. If u ∈ A (respectively, B) then in the next round we can be certain the user will be located in A (respectively, in B). (Note that the sets (i) and (ii) above insure that the user does not escape during the current round.) The search continues inductively on an interval of at most half the size. This implies that the user will be located within O(logn) rounds using O(c) queries per round. This completes the proof of Theorem 3. □

2.2 Planar graphs

As a corollary to Theorem 2 we get the following result for planar graphs with max degree d.

Theorem 4 Suppose that a user begins moving at time 0 from a known location s of a planar graph of maximum degree d. There is an algorithm that will find the user in at most O(logn) rounds with a total of at most O(d\sqrt{n}logn) queries.

Proof (Theorem 4). We use the planar separator theorem of Lipton and Tarjan ([7]): Any n-node planar graph of maximum degree d has an edge separator of size O(d\sqrt{n}). The result follows immediately from Theorem 2. This completes the proof of Theorem 4. □

2.3 Mesh

In this section we give upper bounds for the mesh that improve upon the obvious application of the general algorithms. We prove the following theorem.

Theorem 5 Suppose that a user begins moving at time 0 from a known location s of an n × n mesh. For any fixed r number of rounds there is a search algorithm that starting at time t will find the user in at most O(rmin\{n,t\}^{\frac{2^{r}}{2^{r}−1}} ) queries.

Proof (Theorem 5). Consider the case where n > t. (The case n ≤ t is handled similarly by considering a mesh of side t + r centered at s.) By querying all of the nodes one can find the user in one round using n^{2} queries. We show how to achieve O(n^{4/3}) queries in two rounds and then show how to generalize this result to get the claimed result. On round one we query all nodes on every n^{2/3}rd row and column and their neighbors, a total of less than 6n^{4/3} queries. At this point the search algorithm can deduce which of the resulting n^{2/3}×n^{2/3} submeshes the user is in by following its progress from the submesh containing s and observing which boundaries it crosses when. If all queries are null then the submesh containing s is the correct one. One more round of n^{4/3} queries suffices.

To generalize to r rounds, divide them into two sets of rounds, the first round and the remaining r − 1 rounds and apply the solution for fewer rounds inductively. On round one we query all nodes on every n^{1−1/(2^{r}−1)} = n^{(2^{r}−2)/(2^{r}−1)} rd row and column (and neighbors), a total of at most 6n^{2^{r}/(2^{r}−1)} queries. At this point we can deduce on which of the resulting n^{(2^{r}−2)/(2^{r}−1)} × n^{(2^{r}−2)/(2^{r}−1)} submeshes the user is in The remaining r − 1 rounds are now executed inductively on an m × m submesh containing s, where m = n^{(2^{r}−2)/(2^{r}−1)} . This completes the proof of Theorem 5. □

Applying Theorem 2 directly to the mesh results in an algorithm that uses O(logn) rounds and O(nlogn) queries. By a slight adjustment we can remove the factor of logn.

Theorem 6 Suppose that a user begins moving at time 0 from a known location s of an n × n mesh. There is a search algorithm that starting at time t will find the user in at most O(logmin{n,t}) rounds and at most O(min{n,t}) queries.

Proof (Theorem 6). Consider the case where n > t. (The case n ≤ t is handled similarly by considering a mesh of side t + logt centered at s.) We note that a k × l mesh has an edge separator of size O(min{k,l}) and the resulting graphs after removing the separator are meshes with sides min{k,l} and max{k,l}/2. Applying an algorithm analogous to that of Theorem 2 but at each round rather than querying the separator from the previous rounds, we enlarge the mesh by logn in order to be certain the user does not escape, we get an algorithm that after O(logn) rounds and O(n) queries has reduced the range of the user to a mesh of maximum side O(logn). One round of O(log^{2}n) queries completes the search. This completes the proof of Theorem 6. □

2.4 Tree

In this section we give upper bounds for trees. Direct application of the results for arbitrary graphs provide upper bounds but these can be improved somewhat by taking advantage of the tree topology.

The algorithm of Theorem 1 when adapted to trees of maximum degree d yields the following theorem.

Theorem 7 Suppose that a user begins moving at time 0 from a known location s of a tree of maximum degree d and height h. There is an algorithm that will find the user in at most h rounds with a total of at most O(hd) queries.

Proof (Theorem 7). The search algorithm starts by querying the root of the tree and its neighbors. If none of these nodes has seen the user then it must be located in the same subtree rooted at that child of the root as that in which the start node s is located. Otherwise, we consider the node v that has seen the user most recently. If v is the root then the user has been found! If v is a child of the root then the user must be located in the subtree rooted at v. In this last case, we can detach the subtree rooted at v and iterate the search inductively. In any case, there is a total of at most h rounds and in each round the search algorithm makes at most d + 1 queries. This completes the proof of Theorem 7. □

The algorithm from Theorem 2 when applied to a constant degree tree results in an algorithm that requires O(log^{3}n) queries to find a user in O(logn) rounds. This can be significantly improved as we see in the following theorem.

Theorem 8 Suppose that a user begins moving at time 0 from a known location s of a tree of maximum degree d. There is an algorithm that will find the user in at most O(log_{\frac{d}{d−1}} n) rounds with a total of at most O(log^{2}_{\frac{d}{d−1}} n) queries.

Proof (Theorem 8). We use the fact that a tree of degree d has a single edge that splits the tree into two pieces neither of which is smaller than n/d. Proceeding as in Theorem 2 using this separator rather than a perfect separator, the theorem follows. (Note that on each round all previous separator edges must be queried.) This completes the proof of Theorem 8. □

2.5 Line

In this section we give upper bounds for the line. Applying Theorem 3 yields an algorithm that finds a user in O(logn) rounds using O(logn) queries. This algorithm can be generalized to yield an optimal algorithm for any number of rounds less than logn. In section 3 we show our upper bound is tight. We can show the following theorem.

Theorem 9 Suppose that a user begins moving at time 0 from a known location s of a line of length n. There is a search algorithm that starting at time t will find the user in r rounds with a total of O(r · min{t,n}^{1/r}) queries.

Proof (Theorem 9). Consider the case where t < n. Assume the user started at node 0 and that the line consists of the nodes 0,±1,±2,...,±n/2. If t < n/2, then at time t it can be at any of the 2t + 1 nodes of the closed interval [−t,t].

The search algorithm is executed in rounds and each round involves querying a certain number of nodes. In the first round the algorithm queries the set of nodes {kt^{(r−1)/r} : |k| ≤ t^{1/r}} ∪ {−t,t} and determines an interval, say I_{1}, of size at most t^{(r−1)/r} which is most recently occupied by the user. By induction, assume that in the i-th round the algorithm has determined an interval, say I_{i}, of size at most t^{(r−i)/r} which is most recently occupied by the user. Set m:= t^{(r−i)/r} . In the i+1-st round the algorithm queries a set of m^{1/(r−i)} equally spaced nodes of the interval I_{i} at distance t^{(r−i−1)/r} from each other. Since m^{1/(r−i)} = t^{1/r} the number of queries in this new round is O(t^{1/r}). The user is found at the r-th round by querying all the nodes of the subinterval I_{r}. It follows that r rounds with O(t^{1/r}) queries per round are sufficient to locate the user.

If t ≥ n then at time t the user may be located at any node of the line. A similar proof will work. We leave the details to the reader. This completes the proof of Theorem 9. □

3 Lower Bounds

In this section we present lower bounds that show some of our upper bounds are tight.

3.1 Clique

The following general lower bound is straightforward:

Theorem 10 Suppose that a user begins moving at time 0 from a known location s of an arbitrary graph. Let N_{s}(t) be the set of nodes reachable from s in t steps. Any search algorithm starting at time t > 0 requires at least N_{s}(t) queries in order to find a node in a single round. □

The above shows that the obvious algorithm of querying all nodes of a clique in a single round is optimal.

Theorem 11 Searching for a user on a clique requires n queries in a single round. □

3.2 Line

We show that the algorithm of Theorem 9 is optimal.

Theorem 12 Suppose that a user begins moving at time 0 from a known location s of a line of length n. Any search algorithm starting at time t and finding the user in r rounds requires Ω(r · min{t,n}^{1/r}) queries.

Proof (Theorem 12). Consider the case where t < n/2 and consider the greater than t nodes within distance t of s. By an uncertainty interval we mean an interval any of whose nodes may be occupied by the user based on the current knowledge of a search algorithm, i.e., the results of its queries.

Claim 1 If prior to the execution of the queries at a given round there is an uncertainty interval of length at least L and if during a round a total of q queries are made to nodes of this interval then after the execution of this round there is an uncertainty interval of length at least L/(q + 1).

Proof (Claim 1) Suppose that q nodes, say v_{1} < v_{2} < ···< v_{q}, in the given interval are queried. This divides the interval into q + 1 subintervals [v_{i},v_{i+1} ], i = 0,...,q (where v_{0} and v_{q+1} are the left and right endpoints of the interval) one of which is of size at least L/(q + 1). An adversary can always answer the queries so as to leave the search algorithm with an uncertainty interval of length at least L/(q + 1). For example, the queries may be answered consistent with the user walking directly to the first non-queried node in the large interval and waiting there. This completes the proof of Claim 1.

Now suppose that an algorithm is executed for r rounds and that at round i ≤ r we made exactly q_{i} queries. In view of Claim 1, at the end of the last round r, the uncertainty interval must be of length at least

\frac{2t + 1}{(q_{1}+ 1)(q_{2}+ 1)··· (q_{r} + 1)} .

and the total number of queries is q_{1}+ q_{2}+ ··· + q_{r}. Hence we have to solve the following:

Optimization problem

minimize  q_{1}+ q_{2}+ ··· + q_{r}.
subject to  (q_{1}+ 1)(q_{2}+ 1)··· (q_{r} + 1) ≥ 2t + 1.

It is easy to see that this is minimized when q_{1} = q_{2} = ···= q_{r}, in which case the total number of queries is at least

Ω( r · (2t + 1)^{1/r}) .

If t ≥ n/2 then at time t the user may be located at any node of the line. Therefore a similar proof will work. We leave the details to the reader. This completes the proof of Theorem 12. □

3.3 Mesh

We now show that the upper bound of Theorem 5 is tight for two round protocols. Namely we prove the following result.

Theorem 13 Suppose that a user begins moving at time 0 from a known location s of an n×n mesh. Any search algorithm starting at time t and finding the user in two rounds requires Ω(min{t^{4/3},n^{4/3}}) queries.

Proof (Theorem 13). We prove the result for t = n and s being the center of the mesh. The necessary adjustments when either t > n or t < n and for arbitrary s are easy and are left to the reader. First we prove the following lemma.

Lemma 1 Consider an m × m mesh. Let Q be the set of queries in the first round and assume that q := |Q| < m. There is a connected subgraph A of the mesh of diameter at most 2m such that |A| is in Ω((m − q)^{2}).

Proof (Lemma 1). Remove all nodes in Q as well as all rows and columns containing these nodes. There remain m−q columns and m−q rows of the mesh with no nodes from Q. The size of the resulting set A of nodes is at least (m−q)^{2}. Also the set has diameter at most 2m because you can go from one node to the other by first traversing the row of the first node and then the column of the second. This completes the proof of Lemma 1.

Now we return to the proof of the theorem. Let q be the number of queries in the first round of the search. Without loss of generality we can assume that q < n^{4/3}/4 (otherwise the lower bound in the proof of the theorem is complete). Divide the mesh into n^{2/3} many n^{2/3}×n^{2/3} submeshes. There is a m×m submesh (excluding the submeshes on the perimeter of the mesh), where m = n^{2/3}, such that only at most n^{2/3}/2 queries are asked in this submesh in the first round. Let q be the number of queries asked in this submesh in the first round. By Lemma 1, there is a connected subgraph A of the submesh of diameter at most 2m such that |A| is in Ω(m − q)^{2}). We answer all queries of the first round consistent with the agent having started at time 0 and having walked directly to the nearest node in A and having waited there until time n − 2n^{2/3}. Now, by Theorem 10 at least Ω((m − q)^{2}) = Ω(n^{4/3}) nodes must queried in the second round. This completes the proof of Theorem 13. □

3.4 Arbitrary graphs

A lower bound for arbitrary graphs follows easily from the lower bound for the line.

Theorem 14 Suppose that a user begins moving at time 0 from a known location s of an arbitrary graph with n nodes of maximal degree d and diameter δ. Any search algorithm starting at time t ≤ δ and finding the user in r rounds requires Ω(max{d + 1,rt^{1/r}} queries.

Proof (Theorem 14). The lower bound d + 1 follows from the fact that a node of degree d and all its neighbors must be queried in order to locate the user. For t ≤ δ, the lower bound rt^{1/r} follows from the lower bound for the line and the fact that there exist two nodes at distance δ. This completes the proof of Theorem 14. □

4 Conclusions

In this paper we considered tradeoffs on the number of rounds and queries for tracking a mobile user in a network. We gave several tracking algorithms for arbitrary networks and specific topologies, like, planar graphs, lines, meshes, and trees. We also considered lower bounds for all these types of networks and showed our algorithms are optimal in several cases. Several interesting problems remain, in addition to tightening our bounds. These include variants of the query/answer model we studied here, that are either more or less specific in the information they provide. Additional twists concern modeling the behavior of possibly faulty information (e.g., either an upper bound on the number of nodes that may be liars or nodes may give wrong answers at random) may provide interesting variants for further investigation.

Acknowledgments

Many thanks to Paolo Penna for useful conversations on the subject and to the anonymous referees for their suggestions.

References

[1] B. Awerbuch and D. Peleg. Concurrent online tracking of mobile users. In: Proc. of SIGCOMM 91, pp. 221–233, 1991.

[2] P. Bahl and V.N. Padmanabhan. User Location and Tracking in an In-Building Radio Network. Microsoft Research, Technical Report MSR-TR-99-12, 1999.

[3] A. Bar-Noy and G. Malewicz, Establishing Wireless Conference Call Under Delay Constraints, in Proceedings of ACM PODC 2002.

[4] H. L. Bodlaender, D. M. Thilikos. Computing Small Search Numbers in Linear Time. Technical Report UU-CS-1998-05, Department of Computer Science, Utrecht University, Utrecht, the Netherlands, 1998.

[5] D.G. Jeong and W.S. Jeon. Probabilistic Location Update for Advanced Cellular Mobile Networks. IEEE Communications Letters 1, pp. 8–10, 1998.

[6] D. Knuth, The Art of Computer Programming: Volume 3, Sorting and Searching, Addison Wesley, 3rd ed., 1998.

[7] R. Lipton and R. Tarjan, A Separator Theorem For Planar Graphs. SIAM J. Appl. Math., Vol.36, No 2, April 1979.

[8] Z. Naor and H. Levy. User Tracking in Personal Communication Network: A Traffic Based Approach. In: Workshop Record 2nd International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (in conjunction with ACM/IEEE Mobicom ’98), 1998.

[9] T. D. Parsons, The Search Number of a Connected Graph. Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Math. Publ., Winnipeg (1978) 549-554.

[10] D. M. Thilikos, M. J. Serna and H. L. Bodlaender, A Polynomial Time Algorithm for the Cutwidth of Bounded Degree Graphs with Small Treewidth, Technical Report UU-CS-2001-04. Institute for Information and Computing Sciences, Utrecht University, 2001.

[11] D. M. Thilikos, M. J. Serna and H. L. Bodlaender, A Constructive Linear Time Algorithm for Small Cutwidth and Carving-width, Proc. 11th International Symposium on Algorithms And Computation ISAAC ’00, Lecture Notes in Computer Science 1969, Springer Verlag, pp. 192–203, 2000.

[12] C. Rose and R. Yates. Minimizing the average cost of paging under delay constraints. Wireless Networks 1, pp. 211–219, 1995.

[13] C. Rose and R. Yates. Location uncertainty in mobile networks: A theoretical framework. IEEE Communications Magazine, pp. 94–101, 1997.

[14] A.A. Siddiqi and T. Kunz. The Peril of Evaluating Location Management Proposals through Simulations. unpublished manuscript.

[15] J.Z. Wang. A fully distributed location registration strategy for universal personal communication systems. IEEE J. SAC, Vol. 11, No. 6, pp. 850– 860, 1993.

Evangelos Kranakis School of Computer Science, Carleton University, Ottawa, ON, Canada K1S 5B6. E-mail: kranakis@scs.carleton.ca

Danny Krizanc Department of Mathematics and Computer Sciece, Wesleyan University, Middletown, CT, USA 06459. E-mail: dkrizanc@wesleyan.edu

Sunil Shende Department of Computer Science, Rutgers University, Camden, NJ, USA 08102. E-mail: shende@crab.rutgers.edu