1. A symbolical algorithm on additive basis and double-loop networks
- Author
-
Aguiló, F., Arteaga, D., and Diego, I.
- Subjects
- *
ALGORITHMS , *FINITE, The , *DIRECTED graphs , *BIBLIOGRAPHY - Abstract
A double-loop digraph
G=G(N;s1,s2) , withgcd(N,s1,s2)=1 , has the set of verticesV=ZN and the adjacencies are given byu→u+si (mod N) i=1,2 . The diameter ofG , denoted byD(N;s1,s2) , is known to be lower bounded bylb(N) withThis lower bound is known to be sharp. For a fixedN∈N , some algorithms to findD(N) and steps1⩽α<β such that D(N;α,β)=D(N) are known through the bibliography, being of numerical nature all of them.In this paper we propose a symbolic algorithm on the following problem: Given a number of verticesN0∈N , find if possible an infinite family of tight double-loop digraphsG(x)=G(N(x);s1(x),s2(x)) such thatN(x0)=N0 andD(x)=D(N(x);s1(x),s2(x))=lb(N(x)) ∀x⩾x0 . This family is parameterized by the integerx withN(x)∈Z ands1(x),s2(x)∈Z/(N(x)) . As a direct consequence of such an explicit family of digraphsG(x) , we also have an additive basis{s1(x),s2(x)} which covers the elements ofZ/(N(x)) with optimal order.The time cost of this algorithm isO(√ of N0 log N0) , in the worst case. [Copyright &y& Elsevier]- Published
- 2004
- Full Text
- View/download PDF