Twodimensional bandwidth minimization problem: Exact and heuristic approaches
dc.contributor.author  RodríguezGarcía, Miguel Ángel  
dc.contributor.author  SánchezOro, Jesús  
dc.contributor.author  RodriguezTello, Eduardo  
dc.contributor.author  Monfroy, Éric  
dc.contributor.author  Duarte, Abraham  
dc.date.accessioned  20240208T08:38:18Z  
dc.date.available  20240208T08:38:18Z  
dc.date.issued  20210228  
dc.identifier.citation  RodríguezGarcía, M. Á., SanchezOro, J., RodriguezTello, E., Monfroy, E., & Duarte, A. (2021). Twodimensional bandwidth minimization problem: Exact and heuristic approaches. KnowledgeBased Systems, 214, 106651.  es 
dc.identifier.issn  09507051  
dc.identifier.uri  https://hdl.handle.net/10115/30002  
dc.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) φ∈Φ  es 
dc.description.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 twodimensional 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 runtime 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.  es 
dc.language.iso  eng  es 
dc.publisher  KNOWLEDGEBASED SYSTEMS  es 
dc.subject  Graph layout  es 
dc.subject  Metaheuristics  es 
dc.subject  Variable Neighborhood Search  es 
dc.subject  GRASP  es 
dc.subject  Constraint Programming Formulations  es 
dc.title  Twodimensional bandwidth minimization problem: Exact and heuristic approaches  es 
dc.type  info:eurepo/semantics/article  es 
dc.identifier.doi  10.1016/j.knosys.2020.106651  es 
dc.rights.accessRights  info:eurepo/semantics/restrictedAccess  es 
Files in this item
This item appears in the following Collection(s)

Artículos de Revista [4166]
Los ítems de digitalBURJC están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario