Minimum Spanning Tree in P Systems

摘要：

　　We present the first P system specification for one of the best-known algorithms in distributed computing: synchronous GHS algorithm (SynchGHS) 9, which computes a minimum spanning tree (MST) for a weighted undirected graph, in the synchronous setting. All our algorithms are fixed-size, i.e. the number of P rules does not depend on the number of cells and the membrane structure of the underlying P system. By applying high-level generic rules in matrix grammar mode, we achieve the maximum theoretical performanceone theoretical step is exactly one step in the execution of our P specification.

关键词： Synchronous GHS algorithm Generic rules Matrix grammars Minimum spanning tree Network P system

作者: Huiling Wu

作者单位: Department of Computer Science,University of Auckland,Private Bag 92019,Auckland,New Zealand

会议类型: 国际会议

会议名称: 2013年第二届亚洲膜计算国际会议(2013ACMC)

会议地点: 成都

会议语种:英文

页码: 88-104

在线出版日期: 2013-11-04（万方平台首次上网日期，不代表论文的发表时间）