Two-dimensional bandwidth minimization problem: Exact and heuristic approaches
Fecha
2021-02-28
Título de la revista
ISSN de la revista
Título del volumen
Editor
KNOWLEDGE-BASED SYSTEMS
Resumen
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.
Descripción
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)
φ∈Φ
Palabras clave
Citación
Rodríguez-García, M. Á., Sanchez-Oro, J., Rodriguez-Tello, E., Monfroy, E., & Duarte, A. (2021). Two-dimensional bandwidth minimization problem: Exact and heuristic approaches. Knowledge-Based Systems, 214, 106651.