Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
On the Exact Solution of VSP for General and Structured Graphs: Models and Algorithms
verfasst von : Norberto Castillo-García, Héctor Joaquín Fraire Huacuja, Rodolfo A. Pazos Rangel, José A. Martínez Flores, Juan Javier González Barbosa, Juan Martín Carpio Valadez
Erschienen in: Recent Advances on Hybrid Approaches for Designing Intelligent Systems
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this chapter the vertex separation problem (VSP) is approached. VSP is NP-hard with important applications in VLSI, computer language compiler design, and graph drawing, among others. In the literature there are several exact approaches to solve structured graphs and one work that proposes an integer linear programming (ILP) model for general graphs. Nevertheless, the model found in the literature generates a large number of variables and constraints, and the approaches for structured graphs assume that the structure of the graphs is known a priori. In this work we propose a new ILP model based on a precedence representation scheme, an algorithm to identify whether or not a graph has a Grid structure, and a new benchmark of scale-free instances. Experimental results show that our proposed ILP model improves the average computing time of the reference model in 79.38 %, and the algorithm that identifies Grid-structured graphs has an effectiveness of 100 %.