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.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11391/1530878
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact