Multistart Search for the Cyclic Cutwidth Minimization Problem

Abstract

English: The Cyclic Cutwidth Minimization Problem (CCMP) is a Graph Layout Problem that consists of finding an embedding of the vertices of a candidate graph in a host graph, in order to minimize the maximum cut of a host edge. In this case, the host graph is restricted to be a cycle. In this paper, we identify a new lower bound for the problem, and also a property which allows search procedures to drastically reduce the neighborhood size during the search. Additionally, we propose the use of an alternative objective function for min–max optimization problems, never used before in the context of the CCMP. These strategies have been combined within a multistart search procedure for this problem. The obtained method is compared with the state of the art for the CCMP using sets of problem instances previously published. Statistical tests indicate the merit of our proposal.

Español: El problema de minimización del ancho de corte cíclico (CCMP) es un problema de grados que consiste en encontrar un embebido de los vértices de un grafo candidato en un grafo huésped, con el fin de minimizar el máximo corte de una arista del grafo huésped. En este caso, el grafo huésped se restringe a ser un ciclo. En este artículo, identificamos una nueva cota inferior para el problema, y también una propiedad que permite a los procedimientos de búsqueda reducir drásticamente el tamaño del vecindario durante la búsqueda. Además, proponemos el uso de una función objetivo alternativa para los problemas de optimización min-max, nunca utilizada antes en el contexto del CCMP. Estas estrategias se han combinado dentro de un procedimiento de búsqueda multistart para este problema. El método obtenido se compara con el estado del arte para el CCMP utilizando conjuntos de instancias de problemas publicados anteriormente. Las pruebas estadísticas indican el mérito de nuestra propuesta.