Logo do repositório
 
Publicação

Formulations for the Weight-Constrained Minimum Spanning Tree Problem

2010-09-30Artigo científico Acesso aberto
Ver registo simples
datacite.subject.fosCiências Naturais::Ciências Físicas
dc.contributor.authorRequejo, Cristina
dc.contributor.authorAgra, Agostinho
dc.contributor.authorCerveira, Adelaide
dc.contributor.authorSantos, Eulália
dc.date.accessioned2025-10-30T18:34:22Z
dc.date.available2025-10-30T18:34:22Z
dc.date.issued2010-09-30
dc.descriptionConference name - International Conference on Numerical Analysis and Applied Mathematics 2010, ICNAAM-2010; Conference date - 19 September 2010 - 25 September 2010
dc.description.abstractWe consider the Weight-constrained Minimum Spanning Tree problem (WMST). The WMST aims at finding a minimum spanning tree such that the overall tree weight does not exceed a specified limit on a graph with costs and weights associated with each edge. We present and compare, from the computational point of view, several formulations for the WMST. From preliminary computational results we propose a model that combines a formulation similar to the well known Miller-Tucker-Zemlin formulation with the cut-set inequalities.eng
dc.identifier.citationCristina Requejo, Agostinho Agra, Adelaide Cerveira, Eulália Santos; Formulations for the Weight‐Constrained Minimum Spanning Tree Problem. AIP Conf. Proc. 30 September 2010; 1281 (1): 2166–2169. https://doi.org/10.1063/1.3498397.
dc.identifier.doi10.1063/1.3498397
dc.identifier.eissn1551-7616
dc.identifier.issn0094-243X
dc.identifier.urihttp://hdl.handle.net/10400.8/14435
dc.language.isoeng
dc.peerreviewedyes
dc.publisherAmerican Institute of Physics
dc.relation.hasversionhttps://pubs.aip.org/aip/acp/article/1281/1/2166/846522/Formulations-for-the-Weight-Constrained-Minimum
dc.relation.ispartofAIP Conference Proceedings
dc.rights.uriN/A
dc.subjectminimum spanning tree
dc.subjectweight-constraint
dc.subjectextended formulation
dc.subjectknapsack constraint
dc.titleFormulations for the Weight-Constrained Minimum Spanning Tree Problemeng
dc.typejournal article
dspace.entity.typePublication
oaire.citation.endPage2169
oaire.citation.issue1
oaire.citation.startPage2166
oaire.citation.titleAIP Conference Proceedings
oaire.citation.volume1281
oaire.versionhttp://purl.org/coar/version/c_970fb48d4fbd8a85
person.familyNameSantos
person.givenNameEulália Maria Mota
person.identifierAAO-4024-2020
person.identifier.ciencia-idD515-A6BD-A750
person.identifier.orcid0000-0001-8069-2657
person.identifier.scopus-author-id37089304300
relation.isAuthorOfPublicationef54e890-81e1-4ae4-a2eb-7c64921798f4
relation.isAuthorOfPublication.latestForDiscoveryef54e890-81e1-4ae4-a2eb-7c64921798f4

Ficheiros

Principais
A mostrar 1 - 1 de 1
Miniatura
Nome:
Formulations for the weight-constrained minimum spanning tree problem.pdf
Tamanho:
130.4 KB
Formato:
Adobe Portable Document Format
Descrição:
We consider the Weight-constrained Minimum Spanning Tree problem (WMST). The WMST aims at finding a minimum spanning tree such that the overall tree weight does not exceed a specified limit on a graph with costs and weights associated with each edge. We present and compare, from the computational point of view, several formulations for the WMST. From preliminary computational results we propose a model that combines a formulation similar to the well known Miller-Tucker-Zemlin formulation with the cut-set inequalities.
Ver/Abrir
Licença
A mostrar 1 - 1 de 1
Miniatura indisponível
Nome:
license.txt
Tamanho:
1.32 KB
Formato:
Item-specific license agreed upon to submission
Descrição:
Ver/Abrir

Coleções

ESTG - Artigos em revistas internacionais