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 performance—one 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

会议类型: 国际会议

会议名称: Asian Conference on Membrane Computing (2012亚洲膜计算国际会议)(ACMC2012)

会议地点: 武汉

会议语种:英文

页码: 88-104

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