Type:	Monografia
Title:	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.
Keywords:	Programação linear Solução de problemas
Language:	por
Country:	Brasil
Publisher:	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
Issue Date:	2026
Appears in Collections:	Ciência da Computação

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.