C-semiring Frameworks for Minimum Spanning Tree Problems

DOI10.1007/978-3-642-03429-9_5MaRDI QIDQ3184724zbMATH OpenOpenAlexFDO

Authors Stefano Bistarelli, Francesco Santini

Publication date 22 October 2009

Published in Recent Trends in Algebraic Development Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03429-9_5

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Symbolic computation and algebraic computation (68W30)

Recommendations

• Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs
• An algebraic framework for minimum spanning tree problems
• Spanning cactus: complexity and extensions
• Computational Methods for Minimum Spanning Tree Algorithms
• scientific article; zbMATH DE number 1916666

Cites work

• A new proof of Cayley's formula for counting labeled trees
• Enumeration of Pareto optimal multi-criteria spanning trees - a proof of the incorrectness of Zhou and Gen's proposed algorithm
• Genetic algorithm approach on multi-criteria minimum spanning tree problem
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 1916666 (Why is no real title available?)
• Modelling multicast QoS routing by using best-tree search in and-or graphs and soft constraint logic programming
• Semiring-based constraint satisfaction and optimization
• Semirings for constraint solving and programming.
• Soft constraint logic programming and generalized shortest path problems

Cited in

(4)

• An algebraic framework for minimum spanning tree problems
• Verifying minimum spanning tree algorithms with Stone relation algebras
• Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs
• Relation-algebraic verification of Prim's minimum spanning tree algorithm

This page was built for publication: C-semiring Frameworks for Minimum Spanning Tree Problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3184724)