We define two algebra-based algorithms for solving the Minimum Spanning Tree problem with partially-ordered edges. The parametric structure we propose is a c-semiring, being able to represent different cost-metrics at the same time. We embed c-semirings into the Kruskal and Reverse-delete Kruskal algorithms (thus generalising them), and we suppose the edge costs to be partially ordered. C-semirings can represent multi-criteria MST problems, which are NP-hard to solve. Finally, we test one of the new algorithms to prove its applicability in practice, and we compare it with related work.
Kruskal with embedded C-semirings to solve MST problems with partially-ordered costs
Bistarelli S.;Rossi F.;Santini F.
2021
Abstract
We define two algebra-based algorithms for solving the Minimum Spanning Tree problem with partially-ordered edges. The parametric structure we propose is a c-semiring, being able to represent different cost-metrics at the same time. We embed c-semirings into the Kruskal and Reverse-delete Kruskal algorithms (thus generalising them), and we suppose the edge costs to be partially ordered. C-semirings can represent multi-criteria MST problems, which are NP-hard to solve. Finally, we test one of the new algorithms to prove its applicability in practice, and we compare it with related work.File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
