Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing

DOI10.1016/j.tcs.2006.10.036zbMath1162.90367OpenAlexW2101928097MaRDI QIDQ1022603

Rastislav Královič, Peter Ružička

Publication date: 22 June 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.10.036

zbMATH Keywords

communication networkspacket routingacyclic orientation cover

Mathematics Subject Classification ID

Communication networks in operations research (90B18) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

ACYCLIC ORIENTATIONS ON THE SIERPINSKI GASKET

Cites Work

• Acyclic orientations do not lead to optimal deadlock-free packet routing algorithms
• Deadlock prevention by acyclic orientations
• A group-theoretic model for symmetric interconnection networks
• Layered cross product&mdashA technique to construct interconnection networks
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing