Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

New Dynamic Programming Algorithm for the Multiobjective Minimum Spanning Tree Problem

under review
  • The Multiobjective Minimum Spanning Tree (MO-MST) problem is a variant of the Minimum Spanning Tree problem, in which the costs associated with every edge of the input graph are vectors. In this paper, we design a new dynamic programming MO-MST algorithm. Dynamic programming for a MO-MST instance leads to the definition of an instance of the One-to-One Multiobjective Shortest Path (MOSP) problem and both instances have equivalent solution sets. The arising MOSP instance is defined on a so called transition graph. We study the original size of this graph in detail and reduce its size using cost dependent arc pruning criteria. To solve the MOSP instance on the reduced transition graph, we design the Implicit Graph Multiobjective Dijkstra Algorithm (IG-MDA), exploiting recent improvements on MOSP algorithms from the literature. All in all, the new IG-MDA outperforms the current state of the art on a big set of instances from the literature. Our code and results are publicly available.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Pedro Maristany de las Casas, Antonio Sedeño-Noda, Ralf Borndörfer
Document Type:Article
Parent Title (English):Arxiv Preprint
Date of first Publication:2023/06/23
ArXiv Id:http://arxiv.org/abs/2306.16203
Licence (German):License LogoCreative Commons - CC BY-NC-ND - Namensnennung - Nicht kommerziell - Keine Bearbeitungen 4.0 International
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.