Given a set of
n nodes, each node wants a connection of size
1 to every other node.
Between two nodes can be installed oriented capacities. A capacity of size c costs ca, where a is a real between 0 and 1.
1 - Some asymptotical examples.
Complete oriented graph
For example, the cost of the complete graph Kn with shortest path routing S(Kn) is
Between two nodes can be installed oriented capacities. A capacity of size c costs ca, where a is a real between 0 and 1.
1 - Some asymptotical examples.
Complete oriented graph
For example, the cost of the complete graph Kn with shortest path routing S(Kn) is
Cost(K
n,S(K
n))=n(n-1).
Oriented Ring
The cost of the ring Rn with shortest path routing S(R n) is
The cost of the ring Rn with shortest path routing S(R n) is
Cost(R
n,S(R
n))=n[n(n-1)/2]a.
Star graph
Finally the cost of the star graph Sn with shortest path routing S(Sn) is
2 - Open problem
For a given n, let On be a graph that achieves the minimal cost and ROn its associated routing. We denote
Star graph
Finally the cost of the star graph Sn with shortest path routing S(Sn) is
Cost(Sn
,S(Sn
))=2(n-1)a+1
.
2 - Open problem
For a given n, let On be a graph that achieves the minimal cost and ROn its associated routing. We denote
Optimal(n)=Cost(On,RO
n).
What is the value of
Optimal(n) ? We know for sure that
(n-1)1+a <= Optimal(n) <= 2(n-1) 1+a,
but not much more. For more details, see our report.
(n-1)1+a <= Optimal(n) <= 2(n-1) 1+a,
but not much more. For more details, see our report.