×

Dijkstra, Floyd and Warshall meet Kleene. (English) Zbl 1259.68243


MSC:

68W30 Symbolic computation and algebraic computation
16Y60 Semirings
08A70 Applications of universal algebra in computer science

Software:

Algorithm 97
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Aho AV, Hopcroft JE, Ullman JD (1974) The design and analysis of computer algorithms. Addison-Wesley, USA
[2] Backhouse R, Carré B (1975) Regular algebra applied to path-finding problems. IMA J Appl Math 15(2): 161–186 · Zbl 0304.68082 · doi:10.1093/imamat/15.2.161
[3] Backhouse R, van den Eijnde J, van Gasteren A (1994) Calculating path algorithms. Sci Comput Progr 22(1–2): 3–19 · Zbl 0818.68117 · doi:10.1016/0167-6423(94)90005-1
[4] Bellman R (1958) On a routing problem. Quart Appl Math 16: 87–90 · Zbl 0081.14403
[5] Berge C (1962) The theory of graphs and its applications. Methuen · Zbl 0097.38903
[6] Carré B (1971) An algebra for network routing problems. IMA J Appl Math 7: 273–294 · Zbl 0219.90020 · doi:10.1093/imamat/7.3.273
[7] Carré B (1979) Graphs and networks.Oxford applied mathematics and computing science series. Clarendon Press, Oxford University
[8] Coltun R, Ferguson D, Moy J (2008) OSPF for IPv6. RFC 2328 (Standard, Errata Exist)
[9] Conway J (1971) Regular algebra and finite machines. Chapman and Hall, London · Zbl 0231.94041
[10] Dantzig G (1960) On the shortest route through a network. Manag Sci 6: 187–190 · Zbl 0995.90518 · doi:10.1287/mnsc.6.2.187
[11] Dijkstra E (1959) A note on two problems in connexion with graphs. Numer Mathe 1: 269–271 · Zbl 0092.16002 · doi:10.1007/BF01386390
[12] Davey B, Priestley H (2002) Introduction to lattices and order. Cambridge University Press, London · Zbl 1002.06001
[13] Floyd R (1962) Algorithm 97: Shortest path. Commun ACM 5: 345 · doi:10.1145/367766.368168
[14] Gondran M, Minoux M (1979) Graphes et algorithmes. Eyrolles
[15] Gondran M, Minoux M (1988) Graphs and Algorithms. Wiley · Zbl 1172.05001
[16] Gondran M, Minoux M (2008) Graphs, Dioids and Semirings–new models and algorithms. Springer, Berlin · Zbl 1201.16038
[17] Höfner P, McIver A (2011) Towards an algebra of routing tables. In: de Swart H (ed) Relations and Kleene algebra in computer science, lecture notes in computer science, vol 6663. Springer, Berlin, pp 212–229
[18] Hollenberg M (1998) Equational axioms of test algebra. In: Nielsen M, Thomas W (eds) CSL ’97: selected papers from the 11th international workshop on computer science logic, lecture notes in computer science, vol 1414
[19] Höfner P, Struth G (2007) Automated reasoning in Kleene algebra. In: Pfennig F (ed) Automated deduction, lecture notes in artificial intelligence, vol 4603. Springer, Berlin, pp 279–294 · Zbl 1184.68462
[20] Kleene S (1951) Representation of events in nerve nets and finite automata. Technical Report RM-704, RAND Corporation RAND Research Memorandum
[21] Kleene SC (1952) Introduction to metamathematics. Van Nostrand · Zbl 0047.00703
[22] Kozen D (1994) A completeness theorem for Kleene algebras and the algebra of regular events. Inf Comput 110(2): 366–390 · Zbl 0806.68082 · doi:10.1006/inco.1994.1037
[23] Kozen D (1997) Kleene algebra with tests. ACM Trans Progr Lang Syst 19(3): 427–443 · Zbl 0882.03064 · doi:10.1145/256167.256195
[24] Lengauer T, Theune D (1991) Efficient algorithms for path problems with general cost citeria. In: Leach Albert J, Burkhard Monien B, Rodríguez-Artalejo M (eds) Automata, languages and programming, 18th International colloquium, ICALP91, Madrid, Spain, July 8–12, 1991, proceedings. Lecture notes in computer science vol 510. Springer, Berlin, pp 314–326 · Zbl 0764.68123
[25] Lengauer T, Theune D (1991) Unstructured path problems and the making of semirings (preliminary version). In: Dehne F, Sack J-R, Santoro N (eds) Algorithms and data structures, 2nd workshop WADS ’91, Ottawa, Canada, August 14–16, 1991, proceedings. Lecture notes in computer science, vol 519. Springer, Berlin, pp 189–200 · Zbl 0764.68124
[26] Moy J (1998) OSPF version 2. RFC 2328 (Standard, Errata Exist)
[27] Oran D (1990) IS-IS protocol specification (IETF). RFC 1142 (Informational)
[28] Perkins C, Belding-Royer E, Das S (2003) Ad hoc on-demand distance vector (AODV) routing. RFC 3561 (Experimental)
[29] Roy B (1959) Transitivité et connexité. Comptes Rendus de l’Académie des Sci Paris 249: 216–218
[30] Tarjan R. (1981) A unified approach to path problems. J ACM 28: 577–593 · Zbl 0462.68041 · doi:10.1145/322261.322272
[31] Warshall S (1962) A theorem on boolean matrices. J ACM 9(1): 11–12 · Zbl 0118.33104 · doi:10.1145/321105.321107
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.