Tipo:	Monografia
Título:	A graph-based integer linear programming model for the unbalanced minimum common string partition problem
Autor(es):	Bruel, Laura Mesquita
Primeiro Orientador:	Braga, Andrei de Almeida Sampaio
Resumo:	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.
Palavras-chave:	Programação linear Solução de problemas
Idioma:	por
País:	Brasil
Instituição:	Universidade Federal da Fronteira Sul
Sigla da Instituição:	UFFS
Faculdade, Instituto ou Departamento:	Campus Chapecó
Tipo de Acesso:	Acesso Aberto
URI:	https://rd.uffs.edu.br/handle/prefix/9403
Data do documento:	2026
Aparece nas coleções:	Ciência da Computação

Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.