Kruskal with embedded c-semirings to solve MST problems with partially-ordered costs. (English) Zbl 1516.68057
Summary: 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68W05 | Nonnumerical algorithms |
References:
| [1] | Cormen, T. T.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge, MA, USA · Zbl 1158.68538 |
| [2] | Boruvka, O., O Jistém Problému Minimálním (About a Certain Minimal Problem), Práce Mor. Prírodoved. Spol. v Brne III, 3 (1926), (in Czech, German summary) |
| [3] | Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization, J. ACM, 44, 2, 201-236 (1997) · Zbl 0890.68032 |
| [4] | Bistarelli, S.; Santini, F., C-semiring frameworks for minimum spanning tree problems, (International Workshop on Recent Trends in Algebraic Development Techniques WADT. International Workshop on Recent Trends in Algebraic Development Techniques WADT, LNCS, vol. 5486 (2009), Springer), 56-70 · Zbl 1253.68370 |
| [5] | Bistarelli, S.; Montanari, U.; Rossi, F.; Santini, F., Unicast and multicast qos routing with soft-constraint logic programming, ACM Trans. Comput. Log., 12, 1, 5:1-5:48 (2010) · Zbl 1351.68031 |
| [6] | Mohri, M., Semiring frameworks and algorithms for shortest-distance problems, J. Autom. Lang. Comb., 7, 3, 321-350 (2002) · Zbl 1033.68067 |
| [7] | Edelkamp, S.; Jabbar, S.; Lluch-Lafuente, A., Cost-algebraic heuristic search, (Proceedings, The Twentieth National Conference on Artificial Intelligence (2005), AAAI Press/The MIT Press), 1362-1367 |
| [8] | Sobrinho, J. L., Algebra and algorithms for qos path computation and hop-by-hop routing in the Internet, IEEE/ACM Trans. Netw., 10, 4, 541-550 (2002) |
| [9] | Camerini, P. M.; Galbiati, G.; Maffioli, F., On the complexity of finding multi-constrained spanning trees, Discrete Appl. Math., 5, 1, 39-50 (1983) · Zbl 0498.90078 |
| [10] | Golan, J., Semirings and Affine Equations over Them: Theory and Applications (2003), Kluwer Academic Pub. · Zbl 1042.16038 |
| [11] | Gadducci, F.; Santini, F., Residuation for bipolar preferences in soft constraints, Inf. Process. Lett., 118, 69-74 (2017) · Zbl 1392.68385 |
| [12] | Kruskal, J. B., On the shortest spanning subtree of a graph and the traveling salesman problem, Proc. Am. Math. Soc., 7, 1, 48-50 (1956) · Zbl 0070.18404 |
| [13] | Shor, P. W., A new proof of Cayley’s formula for counting labeled trees, J. Comb. Theory, Ser. A, 71, 1, 154-158 (1995) · Zbl 0826.05036 |
| [14] | Sourd, F.; Spanjaard, O., A multiobjective branch-and-bound framework: application to the biobjective spanning tree problem, INFORMS J. Comput., 20, 3, 472-484 (2008) · Zbl 1243.90206 |
| [15] | Erdős, P.; Rényi, A., On the evolution of random graphs, Bull. Inst. Int. Stat., 38, 4, 343-347 (1961) · Zbl 0106.12006 |
| [16] | Steiner, S.; Radzik, T., Solving the biobjective minimum spanning tree problem using a k-best algorithm (2003), Department of Computer Science, King’s College London, Tech. Rep., Technical Report TR-03-06 |
| [17] | Ruzika, S.; Hamacher, H. W., A survey on multiple objective minimum spanning tree problems, (Algorithmics of Large and Complex Networks (2009), Springer), 104-116 · Zbl 1248.68388 |
| [18] | Perny, P.; Spanjaard, O., A preference-based approach to spanning trees and shortest paths problems, Eur. J. Oper. Res., 162, 3, 584-601 (2005) · Zbl 1065.90064 |
| [19] | Minoux, M., Solving combinatorial problems with combined min-max-min-sum objective and applications, Math. Program., 45, 1-3, 361-372 (1989) · Zbl 0682.90076 |
| [20] | Dell’Amico, M.; Maffioli, F., Combining linear and non-linear objectives in spanning tree problems, J. Comb. Optim., 4, 2, 253-269 (2000) · Zbl 1028.90046 |
| [21] | Dell’Amico, M.; Maffioli, F., On some multicriteria arborescence problems: complexity and algorithms, Discrete Appl. Math., 65, 1-3, 191-206 (1996) · Zbl 0854.68042 |
| [22] | Zhou, G.; Gen, M., Genetic algorithm approach on multi-criteria minimum spanning tree problem, Eur. J. Oper. Res., 114, 1, 141-152 (1999) · Zbl 0945.90009 |
| [23] | Chen, G.; Chen, S.; Guo, W.; Chen, H., The multi-criteria minimum spanning tree problem based genetic algorithm, Inf. Sci., 177, 22, 5050-5063 (2007) · Zbl 1121.90127 |
| [24] | Guo, W.; Chen, G.; Feng, X.; Yu, L., Solving multi-criteria minimum spanning tree problem with discrete particle swarm optimization, (Int. Conf. on Natural Computation, ICNC (2007), IEEE Computer Society), 471-478 |
| [25] | Neumann, F.; Wegener, I., Randomized local search, evolutionary algorithms, and the minimum spanning tree problem, Theor. Comput. Sci., 378, 1, 32-40 (2007) · Zbl 1117.68090 |
| [26] | Arroyo, J. E.C.; Vieira, P. S.; Vianna, D. S., A grasp algorithm for the multi-criteria minimum spanning tree problem, Ann. Oper. Res., 159, 1, 125-133 (2008) · Zbl 1155.90446 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
