C-semiring Frameworks for Minimum Spanning Tree Problems

C-semiring Frameworks for Minimum Spanning Tree Problems. Bistarelli, S. & Santini, F. 2009.
doi abstract bibtex

In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.

@conference{
	11391_143645,
	author = {Bistarelli, Stefano and Santini, Francesco},
	title = {C-semiring Frameworks for Minimum Spanning Tree Problems},
	year = {2009},
	publisher = {Springer},
	volume = {5486},
	booktitle = {Recent Trends in Algebraic Development Techniques, 19th International Workshop, WADT 2008},
	abstract = {In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.},
	doi = {10.1007/978-3-642-03429-9_5},	
	pages = {56--70}
}

Downloads: 0

{"_id":"3CBje3qK2gkLv55By","bibbaseid":"bistarelli-santini-csemiringframeworksforminimumspanningtreeproblems-2009","author_short":["Bistarelli, S.","Santini, F."],"bibdata":{"bibtype":"conference","type":"conference","author":[{"propositions":[],"lastnames":["Bistarelli"],"firstnames":["Stefano"],"suffixes":[]},{"propositions":[],"lastnames":["Santini"],"firstnames":["Francesco"],"suffixes":[]}],"title":"C-semiring Frameworks for Minimum Spanning Tree Problems","year":"2009","publisher":"Springer","volume":"5486","booktitle":"Recent Trends in Algebraic Development Techniques, 19th International Workshop, WADT 2008","abstract":"In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.","doi":"10.1007/978-3-642-03429-9_5","pages":"56–70","bibtex":"@conference{\n\t11391_143645,\n\tauthor = {Bistarelli, Stefano and Santini, Francesco},\n\ttitle = {C-semiring Frameworks for Minimum Spanning Tree Problems},\n\tyear = {2009},\n\tpublisher = {Springer},\n\tvolume = {5486},\n\tbooktitle = {Recent Trends in Algebraic Development Techniques, 19th International Workshop, WADT 2008},\n\tabstract = {In this paper we define general algebraic frameworks for the Minimum Spanning Tree problem based on the structure of c-semirings. We propose general algorithms that can compute such trees by following different cost criteria, which must be all specific instantiation of c-semirings. Our algorithms are extensions of well-known procedures, as Prim or Kruskal, and show the expressivity of these algebraic structures. They can deal also with partially-ordered costs on the edges.},\n\tdoi = {10.1007/978-3-642-03429-9_5},\t\n\tpages = {56--70}\n}\n","author_short":["Bistarelli, S.","Santini, F."],"key":"11391_143645","id":"11391_143645","bibbaseid":"bistarelli-santini-csemiringframeworksforminimumspanningtreeproblems-2009","role":"author","urls":{},"metadata":{"authorlinks":{}},"downloads":0,"html":""},"bibtype":"conference","biburl":"http://www.dmi.unipg.it/~bista/papers/pubblicazioni.bib","dataSources":["GhB5rb8JzW6az3exo"],"keywords":[],"search_terms":["semiring","frameworks","minimum","spanning","tree","problems","bistarelli","santini"],"title":"C-semiring Frameworks for Minimum Spanning Tree Problems","year":2009}