Network Routing on Regular Digraphs and Their Line Graphs

arXiv2305.14058MaRDI QIDQ6437663FDOQ6437663

Publication date: 23 May 2023

Abstract: This paper concerns all-to-all network routing on regular digraphs. In previous work we focused on efficient routing in highly symmetric digraphs with low diameter for fixed degree. Here, we show that every connected regular digraph has an all-to-all routing scheme and associated schedule with no waiting. In fact, this routing scheme becomes more efficient as the diameter goes down with respect to the degree and number of vertices. Lastly, we examine the simple scheduling algorithm called ``farthest-distance-first and prove that it yields optimal schedules for all-to-all communication in networks of interest, including Kautz graphs.

Mathematics Subject Classification ID

Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20)

This page was built for publication: Network Routing on Regular Digraphs and Their Line Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437663)