| Orderly Algorithm to Enumerate Central Groupoids and Their Graphs |
| |
| 作者姓名： | Tim BOYKETT |
| |
| 作者单位： | Time＇s Up Research Department and Department of Mathematics, Johannes-Kepler University, Linz, Austria |
| |
| 基金项目： | The author is supported in part by Project P15691 from the Austrian Federal FWF, the national science finding body, as well as by several ongoing grants from Stadt Linz, Land 0berSsterreich and the Austrian Federal BKA. Kuust. The author would like to thank Leonard Soicher, who invited him to speak about this work and gave the necessary impulse to get the results written down. |
| |
| 摘 要： | A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes. This paper reiterates Royle and MacKay＇s technique for constructing orderly algorithms. We wish to use this technique to enumerate all UPP2 graphs of small orders 3^2 and 4^2. We attempt to use the direct graph formalism and find that the algorithm is inefficient.
We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are able to design an orderly algorithm to determine all UPP2 graphs of order 3^2, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 4^2 in the near future.
|
| 关 键 词： | 中心广群 有向图 有序算法 列举 |
| 收稿时间： | 18 March 2004 |
| 修稿时间： | 2004-03-182005-04-30 |
Orderly Algorithm to Enumerate Central Groupoids and Their Graphs |
| |
| Tim BOYKETT.Orderly Algorithm to Enumerate Central Groupoids and Their Graphs[J].Acta Mathematica Sinica,2007,23(2):249-264. |
| |
| Authors: | Tim Boykett |
| |
| Institution: | (1) Time’s Up Research Department and Department of Mathematics, Johannes–Kepler University, Linz, Austria |
| |
| Abstract: | A graph has the unique path property UPPn if there is a unique path of length n between any ordered pair of nodes.
This paper reiterates Royle and MacKay’s technique for constructing orderly algorithms. We wish to use this technique to enumerate
all UPP2 graphs of small orders 32 and 42. We attempt to use the direct graph formalism and find that the algorithm is inefficient.
We introduce a generalised problem and derive algebraic and combinatoric structures with appropriate structure. Then we are
able to design an orderly algorithm to determine all UPP2 graphs of order 32, which runs fast enough. We hope to be able to determine the UPP2 graphs of order 42 in the near future.
The author is supported in part by Project P15691 from the Austrian Federal FWF, the national science finding body, as well
as by several ongoing grants from Stadt Linz, Land Ober¨osterreich and the Austrian Federal BKA. Kunst |
| |
| Keywords: | orderly algorithms paths in directed graphs enumeration |
| 本文献已被 维普 SpringerLink 等数据库收录！ |
