Problem Description

Let G = (V, E) be an undirected graph, where V denotes the set of vertices and E the set of edges. Let n = |V| and m = |E|. A labeling f of the vertices of G is a one-to-one mapping from the set V onto the integers {1, 2, . . . , n}, i.e. each vertex v in V has a unique label f(v) in {1, 2, . . . , n}. Note that each labeling can be identified with a permutation of {1, 2, . . . , n}.

In some practical problems it is interesting to maximize the minimum difference between adjacent vertices. For example, if the vertices of the graph G represent sensitive facilities or chemicals, then placing them too close together can be risky. This optimization problem is dual to the well-known bandwidth problem and it is commonly known as the antibandwidth problem, also known as the separation problem (Leung et al., 1984) and the dual bandwidth problem (Yixun and Jinjiang, 2003).

Given a graph G and a labeling f, the antibandwidth AB_f(G) of f is defined as:

AB_f(G) = min{AB_f(v) : v in V}

where AB_f(v) = min{|f(u) − f(v)| : u in N(v)} is the antibandwidth of vertex v and N(v is the set of its adjacent vertices. Then, the Antibandwidth reduction problem consists in maximizing the value of AB_f(G) over all possible labelings

State of the Art Methods

Previous papers on the antibandwidth problem where devoted to the theoretical study of its properties to find optimal solutions for special cases. In the variant studied in Leung et al. (1984), the problem consists in finding a labeling f with a value AB_f(G) greater than a predetermined value k. The authors determined the NP-completeness of this problem and give polynomial time algorithms for several classes of graphs. Yixun and Jinjiang (2003) proposed several upper bounds for AB(G). Some of them are related to the independent and chromatic numbers of G. The bound UB1 is computed as a function of the minimum degree (mind) and maximum degree (maxd) of G.

where mind = min |N(u)| and maxd = max |N(u)| with u int V.

A weaker upper bound, UB2, is computed as a function of the number n of vertices and the number m of edges:

Raspaud et al. (2009) solve the antibandwidth problem for several classes of special graphs: two dimensional meshes (Cartesian product of two paths), tori (Cartesian product of two cycles), and hypercubes. Torok and Vrto (2007) extended these results to the case of three dimensional meshes. More recently, Dobrev et al. (2009) derive tight upper bounds for general Hamming graphs and optimal solution values for a special class of these graphs. Until now, no heuristic has been proposed to obtain high-quality solutions for the antibandwidth problem on general graphs.

Instances

In this section several instance sets are described. These intance set have been used in the related literature to compare the performance of methods for the Antibandwidth Problem:

• Harwell-Boeing Graphs: This data set consists of 24 instances (12 smaller and 12 larger) derived from the Harwell-Boeing Sparse Matrix Collection. Graphs are derived from these matrices as follows. Let Mij denote the element of the i-th row and j-th column of the n×n sparse matrix M. The corresponding graph has n vertices. Edge (i, j) exists in the graph if and only if Mij is not equal to 0. These instances were used in Duarte et al. (2010) with name Harwell-Boeing. Download.
• Grid Graphs: This data set consists of 24 (12 smaller and 12 larger) matrices constructed as the Cartesian product of two paths (Raspaud et al., 2009). They are also called twodimensional meshes and, as documented in Raspaud et al. (2009), the optimal solutions of the antibandwidth problem for these types of instances are known by construction. These instances were used in Duarte et al. (2010) with name Grid Graphs. Download.
• Hamming Graphs: This data set consists of 24 graphs (12 smaller and 12 larger) constructed as the Cartesian product of d complete graphs K_nk, for k = 1, 2, . . . , d (Dobrev et al.,2009). The vertices in these graphs are d-tuples (i₁, i₂, . . . , i_d), where i_k in {0, 1, . . . , n_k−1}. Two vertices (i₁, i₂, . . . , i_d) and (j₁, j₂, . . . , j_d) are adjacent if and only if the two tuples differ in exactly one coordinate. These graphs as referred to as Hamming graphs. It is shown in Dobrev et al. (2009) that if d ≥ 2 and 2 ≤ n1 ≤ n1 ≤ · · · ≤ nd, then the optimal solution of the antibandwidth problem for this type of instance can be calculated. These instances were used inDuarte et al. (2010) with name Grid Graphs. Download.
• Paths: This data set consists of 24 graphs constructed as a linear arrangement of vertices such that every vertex has a degree of two, except the first and the last vertex that have a degree of one. The size of these instances ranges from 50 to 1000. Download.
• Cycles: This data set consists of 24 graphs constructed as a circular arrangement of vertices such that every vertex has a degree of two. The size of these instances ranges from 50 to 1000. Download.
• Toroidal grids: This data set consists of 37 graphs constructed as the Cartesian product of two cycles (i.e., C n × C n ). The size of these instances ranges from 16 to 1600. Download.
• Hypercubes: This data set consists of seven hypercubes Q d . Each vertex is represented as a binary vector of length d. Two vertices are adjacent if their associated binary vectors only differ in one element. Download.
• Complete binary trees: This data set consists of 24 trees, where every tree-level is completely filled except possibly the last level and all nodes are as far left as possible. The size of these instances ranges from 30 to 950. Download.
• Caterpillars: This data set consists of 40 graphs. Each caterpillar, P n 1 n 2 is constructed using the path P n 1 and n 1 copies of the path P n 2 (usually referred to as “hairs”), where each vertex i in P n 1 is connected to the first vertex of the i-th copy of the path P n 2 . The size of these instances ranges from 20 to 1000. Download.
• 3D grids: This data set consists of 8 graphs constructed as the Cartesian product of three paths P n 1 , P n 2 and P n 3 (Raspaud et al. 2009). The size of these instances ranges from 27 to 1000. They are also called three dimensional meshes or cuboidal meshes. Download.

Computational Experience

We have performed an intensive experimentation with the best known heuristic to compute the best known values for the instances. We have also reviewed related literature searching for better values than these. The final best known values for the instances can be downloaded in Excel.

References

• Dobrev, S., R. Kralovic, D. Pardubska, L. Torok, and I. Vrto. Antibandwidth and cyclic antibandwidth of Hamming graphs. Electronic Notes in Discrete Mathematics, 34:295–300, 2009.
• Duarte, A. and R. Martí, M.G.C. Resende and R.M.A. Silva. GRASP with Path Relinking for the Antibandwidth Problem", Networks. In press, 2010.
• Lozano, M., Duarte, A., Gortázar, F., and Martí, R. "Variable neighborhood search with ejection chains for the antibandwidth problem", Journal of Heuristics, 18(6), 919--938, 2012.
• Donnelly, S., and G. Isaak. Hamiltonian powers in threshold and arborescent comparability graphs.
• Discrete Mathematics, 202:33–44, 1999.
• Leung, J.Y.-T., O. Vornberger, and J.D. Witthoff. On some variants of the bandwidth minimization problem. SIAM J. on Computing, 13:650–667, 1984.
• Raspaud, A.,, H. Schroder, O. Sykora, L. Torok, and I. Vrto. Antibandwidth and cyclic antibandwidth of meshes and hypercubes. Discrete Mathematics, 309: 3541–3552, 2009.
• Torok, L., and I. Vrto. Antibandwidth of 3-dimensional meshes. Electronic Notes in Discrete Mathematics, 28:161–167, 2007.
• L. Yixun and Y. Jinjiang. The dual bandwidth problem for graphs. J. of Zhengzhou University, 35:1–5, 2003.