Type:	Monografia
Título :	A graph-based integer linear programming model for the unbalanced minimum common string partition problem
Author:	Bruel, Laura Mesquita
First advisor:	Braga, Andrei de Almeida Sampaio
Resume:	The MinimumCommon StringPartition Problem(MCSP)consistsoffindingaminimum common partition between two related strings. This problem has applications in Computational Biology, wherein a string can represent a genome. The MCSP and its variants, which consider relevant information from genomes, are NP-hard and have already been addressed using heuristics and integer linear programming (ILP). There are ILP models that have been successfully applied to the MCSP and adaptations of these models to solve its variants have shown great results. Motivated by these results, in this paper, a Graph-Based ILP model to the MCSP was adapted to solve the Unbalanced Minimum Common String Partition Problem (UMCSP).Theexperimental results show that the adapted model can be similar or outperform existing ILP models to the UMCSP.
Palabras clave :	Programação linear Solução de problemas
Language:	por
Country:	Brasil
Editorial :	Universidade Federal da Fronteira Sul
Acronym of the institution:	UFFS
College, Institute or Department:	Campus Chapecó
Type of Access:	Acesso Aberto
URI :	https://rd.uffs.edu.br/handle/prefix/9403
Fecha de publicación :	2026
Aparece en las colecciones:	Ciência da Computação

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.