基于闭半环的若干图算法  

Some Graph Algorithms Based on Closed Semirings

作　　者：罗奇鸣[1] 

机构地区：[1]中国科学技术大学计算机科学与技术学院,合肥230027

出　　处：《小型微型计算机系统》2015年第12期2671-2674,共4页Journal of Chinese Computer Systems

基　　金：MOE-MS多媒体计算与通信实验室基金项目(07122807)资助

摘　　要：闭半环是在半环上添加了传递闭包运算符而得到的代数结构.闭半环为计算机科学理论中多个看起来不相关的问题提供了统一的求解理论框架.有不少图算法问题可以通过对图的邻接矩阵在特定的闭半环上计算闭包而求解.本文分析了三个典型的问题:最可靠路径、最小生成树和到达定值数据流分析.其中到达定值数据流分析可采用两种闭半环求解.本文为这些问题提供了基于Haskell语言的算法实现,并为最小生成树问题证明了算法的正确性.Closed semiring is an algebric structure obtained by adding the closure operator to a semiring. Closed semiring provides a u- nified theoretical framework for solving many seemingly unrelated problems in theoretical computer science. Quite a few problems of graph algorithms can be solved by computing the closure of the adajency matrix on a specific dosed semiring. This paper analyzes three typical problems：most reliable paths, minimum spanning tree and reaching definitions dataflow analysis. Reaching definitions dat- aflow analysis can be solved by applying two kinds of closed semirings. This paper provides the Haskell implementation of the algo- rithms for these problems, and proves the correctness of the algorithm for minimum spanning tree.

关 键 词：闭半环 图算法 闭包 HASKELL 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]