We consider the so-called order/degree problem, that is, to determine the smallest diameter of a digraph given order and maximum out-degree. There is no general efficient algorithm known for the construction of such optimal digraphs but various construction techniques for digraphs with minimum diameter have been proposed. In this paper, we survey the known techniques.
展开▼
