We present a method to identify superfluous edge sets in the de Bruijn and Kautz graphs —two classical types of directed graphs — of cardinality at least C ε (Δ – ε)D , with D the graph’s diameter, and Δ its maximum out-degree.
Additionally, we extend this approach to the underlying graph of the line digraph of any digraph G, replacing Δ – ε with the Perron-Frobenius eigenvalue of G.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne