We generalize the matroid-theoretic approach to greedy algorithms to the setting of poset matroids, in the sense of Barnabei, Nicoletti and Pezzoli (1998). We illustrate our result by providing a generalization of Kruskal algorithm (which finds a minimum spanning subtree of a weighted graph) to abstract simplicial complexes.
Greedy algorithms and poset matroids / Luca Ferrari. - In: JOURNAL OF DISCRETE ALGORITHMS. - ISSN 1570-8667. - STAMPA. - 29:(2014), pp. 21-26. [10.1016/j.jda.2014.07.005]
Greedy algorithms and poset matroids
FERRARI, LUCA
2014
Abstract
We generalize the matroid-theoretic approach to greedy algorithms to the setting of poset matroids, in the sense of Barnabei, Nicoletti and Pezzoli (1998). We illustrate our result by providing a generalization of Kruskal algorithm (which finds a minimum spanning subtree of a weighted graph) to abstract simplicial complexes.
File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
JDA_564 (1).pdf
Accesso chiuso
Descrizione: articolo principale
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Tutti i diritti riservati
Dimensione
506.18 kB
Formato
Adobe PDF
|
506.18 kB | Adobe PDF | Richiedi una copia |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
