We investigate the relationship between two kinds of vertex colorings of hypergraphs: unique-maximum (UM) colorings and conflict-free (CF) colorings. In a UM coloring, the colors are ordered, and in every hyperedge of the hypergraph the maximum color in the hyperedge occurs in only one vertex of the hyperedge. In a CF coloring, in every hyperedge of the hypergraph there exists a color in the hyperedge that occurs in only one vertex of the hyperedge. We consider the corresponding UM and CF chromatic numbers and investigate their relationship in arbitrary hypergraphs. Then, we concentrate on hypergraphs that are induced by simple paths in tree graphs.

Given a geometric hypergraph (or a range-space) H=(V,E), a coloring of its vertices is said to be conflict-free if for every hyperedge S ∈ E there is at least one vertex in S whose color is distinct from the colors of all other vertices in S. The study of this notion is motivated by frequency assignment problems in wireless networks. We study the list-coloring (or choice) version of this notion. In this version, each vertex is associated with a set of (admissible) colors and it is allowed to be colored only with colors from its set. List coloring arises naturally in the context of wireless networks. Our main result is a list coloring algorithm based on a new potential method. The algorithm produces a stronger unique-maximum coloring, in which colors are positive integers and the maximum color in every hyperedge occurs uniquely. As a corollary, we provide asymptotically sharp bounds on the size of the lists required to assure the existence of such unique-maximum colorings for many geometric hypergraphs (e.g., discs or pseudo-discs in the plane or points with respect to discs). Moreover, we provide an algorithm, such that, given a family of lists with the appropriate sizes, computes such a coloring from these lists.

A token is hidden in one of several boxes and then the boxes are locked. The probability of placing the token in each of the boxes is known. A searcher is looking for the token by unlocking boxes where each box is associated with an unlocking cost. The searcher conducts its search in rounds and must find the token in a predetermined number of rounds. In each round, the searcher may unlock any set of locked boxes concurrently. The optimization goal is to minimize the expected cost of unlocking boxes until the token is found. The motivation and main application of this game is the task of paging a mobile user (token) who is roaming in a zone of cells (boxes) in a cellular network system. Here, the unlocking costs reflect cell congestions and the placing probabilities represent the likelihood of the user residing in particular cells. Another application is the task of finding some data (token) that may be known to one of the sensors (boxes) of a sensor network. Here, the unlocking costs reflect the energy consumption of querying sensors and the placing probabilities represent the likelihood of the data being found in particular sensors. In general, we call mobile data any entity that has to be searched for.

We investigate deterministic algorithms for a frequency assignment problem in cellular networks. The problem can be modeled as a special vertex coloring problem for hypergraphs: In every hyperedge there must exist a vertex with a color that occurs exactly once in the hyperedge (the conflict-free property). We concentrate on a special case of the problem, called conflict-free coloring for intervals. We introduce a hierarchy of four models for the aforesaid problem: (i) static, (ii) dynamic offline, (iii) dynamic online with absolute positions, and (iv) dynamic online with relative positions. In the dynamic offline model, we give a deterministic algorithm that uses at most log 3/2 n + 1 ≈ 1.71 log 2 n colors and show inputs that force any algorithm to use at least 3 log 5 n + 1 ≈ 1.29 log 2 n colors. For the online absolute-positions model, we give a deterministic algorithm that uses at most 3⌈log 3 n ⌉ ≈ 1.89 log 2 n colors. To the best of our knowledge, this is the first deterministic online algorithm using O (log n ) colors in a nontrivial online model. In the online relative-positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the first-fit greedy online algorithm. We also consider conflict-free coloring only with respect to intervals that contain at least one of the two extreme points.

No abstract available.

This paper studies deterministic algorithms for a frequency assignment problem in cellular networks. A cellular network consists of fixed-position base stations and moving agents. Each base station operates at a fixed frequency, and this allows an agent tuned at this frequency to communicate with the base station. Each agent has a specific range of communication (described as a geometric shape, e.g., a disc) that may contain one or several base stations. To avoid interference, the goal is to assign frequencies to base stations such that for any range, there exists a base station in the range with a frequency that is not reused by some other base station in the range. The base station with this unique (in the range) frequency serves the aforementioned range. Since using many frequencies is expensive, the optimization goal is to use as few frequencies as possible. The problem can be modeled as a special coloring problem for hypergraphs. Base stations are the vertices, ranges are the hyperedges, and colors (frequencies) must be assigned to vertices following the conflict-free property: In every hyperedge there is a color that occurs exactly once.We concentrate on the special case where the n base stations lie on the real line and ranges are the n(n+1)/2 nonempty subsets of consecutive points. This problem is called conflict-free coloring for intervals. We introduce a hierarchy of four models for the above problem: (i) the static model, where the complete hypergraph is given and all vertices are colored simultaneously, (ii) the dynamic offline model, where the vertices appear in some order and the conflict-free property has to be maintained at all times, (iii) the online absolute positions model where the order is revealed in an online fashion and the final hypergraph and positions are known, and (iv) the online relative positions model where there is no knowledge about the final hypergraph and the final positions of vertices.In the case of intervals, the hierarchy is strict. In the dynamic offline model, we give a deterministic algorithm that uses at most log3/2 n+1 colors and exhibit inputs that force any algorithm to use at least 2 log3 n + 1 colors. For the online absolute positions model, we give two deterministic algorithms that use at most 2⌊log2(n + 1)⌋ and 3⌈log3 n⌉ colors, respectively. To the best of our knowledge, these are the first O(log n) deterministic online algorithms, in a non-trivial model. In the online relative positions model, we resolve an open problem by showing a tight analysis on the number of colors used by the natural greedy online algorithm, that at each step uses the smallest color possible. In the case of conflict-free coloring only with respect to intervals that contain either of the two extreme points, we show a strong separation between static and dynamic models and we provide tight bounds for all four models up to an additive term of two.