Abstract Given two nonnegative integers h and k, an L(h, k)‐labeling of a graph G = (V, E) is a map from V to a set of integer labels such that adjacent vertices receive labels at least h apart, while vertices at distance at most 2 receive labels at least k apart. The goal of the L(h, k)‐labeling problem is to produce a legal labeling that minimizes the largest label used. Since the decision version of the L(h, k)‐labeling problem is NP‐complete, it is important to investigate classes of graphs for which the problem can be solved efficiently. Along this line of thought, in this article we deal with co‐comparability graphs, its subclass of interval graphs, and circular‐arc graphs. To the best of our knowledge, ours is the first reported result concerning the L(h, k)‐labeling of co‐comparability and circular‐arc graphs. In particular, we provide the first algorithm to L(h, k)‐label co‐comparability, interval, and circular‐arc graphs with a bounded number of colors. Finally, in the special case where k = 1 and G is an interval graph, our algorithm improves on the best previously‐known ones using a number of colors that is at most twice the optimum. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Summary form only given. We study conflict-free data distribution schemes in parallel memories in multiprocessor system architectures. Given a host graph G, the problem is to map the nodes of G into memory modules such that any instance in G of a template type T can be accessed without memory conflicts. A conflict occurs if two or more nodes of T are mapped to the same module. The mapping algorithm should be fast in terms of data access, minimize the required number of memory modules, and guarantee load balancing on the modules. We consider conflict-free access to star templates (i.e., any node of G along with all its neighbors) and we study the star-access problem on two specific host graphs, tori and hypercubes. We propose conflict-free mappings that are fast and load-balanced, using an optimal or provably good number of memory modules.

The main contribution of this work is to offer a simple and cost-efficient parallel algorithm that, given an arbitrary n-vertex cubic graph G as input, produces an orthogonal grid drawing of G in O(log n) time, using n processors on an EREW PRAM. Our algorithm matches the time and cost performance of the best previously-known algorithm while at the same time improving the constant factors involved in two important metrics: layout area and number of bends. More importantly, however, our algorithm stands out by its conceptual simplicity and ease of implementation.