As the number of autonomous cars grows explosively, it is important to broadcast messages with less time and fewer transmissions, especially emergency messages. Therefore, we present an efficient way to broadcast messages by recording the information of informed and uninformed nodes and adopt the mechanism into the push-pull algorithm for vehicular ad hoc networks.

We study the problem of embedding a guest graph into an optimally-sized grid with minimum edge-congestion. Based on a well-known notion of graph separator, we prove that any guest graph can be embedded with a smaller edge-congestion as the guest graph has a smaller separator, and as the host grid has a higher dimension. Our results imply the following: An N-node planar graph with maximum node degree Delta can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Delta2log N) if d = 2, O(Delta2log log N) if d = 3, and O(Delta2) otherwise. An N-node graph with maximum node degree Delta and a treewidth O(1), such as a tree, an outerplanar graph, and a series-parallel graph, can be embedded into an N-node d-dimensional grid with an edge-congestion of O(Delta) for d ges 2.

We study the online file allocation problem on ring networks. In this paper, we present a 7-competitive randomized algorithm against an adaptive online adversary on uniform ring networks. The algorithm is deterministic if the file size is 1. Moreover, we obtain lower bounds of 4.25 and 3.833 for a deterministic algorithm and a randomized algorithm against an adaptive online adversary, respectively, on ring networks.

In this paper we consider the VLSI layout (i.e., Manhattan layout) of graphs into grids with minimum width (i.e., the length of the shorter side of a grid)as well as with minimum area. The layouts into minimum area and minimum width are equivalent to those with the largest possible aspect ratio of a minimum area layout. Thus such a layout has merits that, by "folding" the layout, a layout of all possible aspect ratio can be obtained with increase of area within a small constant factor. We show that an N-vertex tree with layout-width (i.e., the minimum width of a grid into which the tree can be laid out) k can be laid out into a grid of area O(N) and width O(k). For binary tree layouts, we give a detailed trade-off between area and width: an N-vertex binary tree with layout-width k can be laid out into area O(k+α/1+αN) and width k+α, where α is an arbitrary integer with 0≤ α≤√N, and the area is existentially optimal for any k≥ 1 and α≥ 0. This implies that α=ω(k) is essential for a layout of a graph into optimal area. The layouts proposed here can be constructed in polynomial time. We also show that the problem of laying out a given graph G into given area and width, or equivalently, into given length and width is NP-hard even if G is restricted to a binary tree.

We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hypercube of dimension 6⌈log N⌉ if the maximum degree of a vertex in G is no more than 6⌈log N⌉. Bhatt et al. showed that every N-vertex binary tree can be embedded in a hypercube of dimension ⌈log N⌉ with O(1) congestion. In this paper, we extend the results above and show the following: (1) Every N-vertex graph G can be embedded with unit congestion in a hypercube of dimension 2⌈log N⌉ if the maximum degree of a vertex in G is no more than 2⌈log N⌉, and (2) every N-vertex binary tree can be embedded in a hypercube of dimension ⌈log N⌉ with congestion at most 5. The former answers a question posed by Kim and Lai. The latter is the first result that shows a simple embedding of a binary tree into an optimal-sized hypercube with an explicit small congestion of 5. This partially answers a question posed by Bhatt et al. The embeddings proposed here are quite simple and can be constructed in polynomial time. © 1999 John Wiley & Sons, Inc. Networks 33: 71–77, 1999