A new heuristic algorithm for the vertex separation problem

Simple item page
AudienciaPúblico en generales_ES
CoberturaMéxicoes_ES
Fecha de ingreso2026-10-05T16:34:16Z
Fecha de publicación2018-01-01
ResumenThe Vertex Separation Problem (VSP) belongs to a family of graph layout problems. VSP consists in finding a linear ordering of the vertices of a graph such that the maximum number of vertex separators at each position of the ordering is minimized. This problem has important practical applications in fields such as very large scale integration design, computer language compiler design or natural language processing. VSP has been proven to be NP-hard. In the literature reviewed, we found several heuristic and metaheuristic algorithms designed for solving large instances of VSP. As far as we are aware, these algorithms do not use fuzzy logic. In this chapter, we adapt two fuzzy logic classifiers (FLC) to a constructive algorithm from the literature. More precisely, the first FLC is used to select the vertex to be placed at the first position of the linear ordering according to the adjacency degree. The second FLC is used to select the following vertices according to the number of vertex separators. We have designed five variants of our fuzzy heuristic. The computational experiment indicates that the first four variants have a similar behavior in solution quality and execution time.es_ES
Doihttps://doi.org/10.1007/978-3-319-71008-2_35es_ES
URIhttps://riuat.uat.edu.mx/handle/123456789/6023
Idiomaenes_ES
EditorialSpringer Verlages_ES
RelaciónStudies in Computational Intelligencees_ES
URL relacionadohttps://doi.org/10.1007/978-3-319-71008-2_35es_ES
DerechosAcceso restringido / Suscripción (Metadatos de producción científica)es_ES
Licenciahttp://purl.org/coar/access_right/c_16eces_ES
FuenteStudies in Computational Intelligence
Palabra claveConstructive algorithmses_ES
Palabra claveFuzzy logic classifieres_ES
Palabra claveHeuristicses_ES
Palabra claveVertex separation problemes_ES
TítuloA new heuristic algorithm for the vertex separation problemes_ES
TipoCapítulo Libroes_ES
ArbitradoHa sido Arbitradoes_ES
AutorCastillo-García, Norberto
AutorHernández Hernández, Paula
AutorCastillo-García, Norbertoes_ES
AutorHernández Hernández, Paulaes_ES
InstituciónUniversidad Autónoma de Tamaulipas
InstituciónUniversidad Autónoma de Tamaulipases_ES
Rango de páginas487-500es_ES
URL relacionadahttps://doi.org/10.1007/978-3-319-71008-2_35
Tipo de artículoIndexado
Tipo de artículoIndexadoes_ES
Volumen749es_ES

Files

Collections

Documentación Cientifica