# Two-dimensional bandwidth minimization problem: Exact and heuristic approaches

Abstract

Reducing the bandwidth in a graph is an optimization problem which has generated significant attention over time due to its practical application in Very Large Scale Integration (VLSI) layout designs, solving system of equations, or matrix decomposition, among others. The bandwidth problem is considered as a graph labeling problem where each vertex of the graph receives a unique label. The target consists in finding an embedding of the graph in a line, according to the labels assigned to each vertex, that minimizes the maximum distance between the labels of adjacent vertices. In this work, we are focused on a 2D variant where the graph has to be embedded in a two-dimensional grid instead. To solve it, we have designed two constructive and three local search methods which are integrated in a Basic Variable Neighborhood Search (BVNS) scheme. To assess their performance, we have designed three Constraint Satisfaction Problem (CSP) models. The experimental results show that our CSP models obtain remarkable results in small or medium size instances. On the other hand, BVNS is capable of reaching equal or similar results than the CSP models in a reduced run-time for small instances, and it can provide high quality solutions in those instances which are not optimally solvable with our CSP models. (C) 2020 Elsevier B.V. All rights reserved.

Description

The bandwidth minimization problem (BMP) and its variants have been extensively studied in the literature for their applica- tions in the context of circuit layout, Very Large Scale Integration (VLSI) design, or network communications [1–3]. Formally, this family of problems is defined as follows. Let H = (VH , EH ) and G = (VG,EG) be a host graph and a guest graph, respectively, and let φ be an injective function (usually known as labeling or embedding) of the guest graph to the host graph, i.e., φ : VG −→ VH . Then, the bandwidth (cost) of this labeling is computed as: B(G,φ)= max dH(φ(u),φ(v)), (1) (u,v)∈EG where the function dH (x, y) computes the distance between x and y in H. The optimal bandwidth of G, relative to the host graph H, is then defined as the minimum B(G, φ) value considering the set of all possible labelings Φ of G. In mathematical terms, B⋆(G) = min B(G, φ) . (2) φ∈Φ

Collections

- Artículos de Revista [4088]

Los ítems de digital-BURJC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario