7 papers
Towards Universally Optimal Shortest Paths Algorithms in the Hybrid Model
Philipp Schneider
A drawback of the classic approach for complexity analysis of distributed graph problems is that it mostly informs about the complexity of notorious classes of ``worst case'' graph…
Near Tight Shortest Paths in the Hybrid Model
Philipp Schneider
Shortest paths problems are subject to extensive studies in classic distributed models such as the CONGEST or Congested Clique. These models dictate how nodes may communicate in or…
Routing Schemes for Hybrid Communication Networks
Sam Coy, Artur Czumaj, Christian Scheideler +2
We consider the problem of computing routing schemes in the model of distributed computing where nodes have access to two fundamentally different communication mo…
Near-Shortest Path Routing in Hybrid Communication Networks
Sam Coy, Artur Czumaj, Michael Feldmann +5
Hybrid networks, i.e., networks that leverage different means of communication, become ever more widespread. To allow theoretical study of such networks, [Augustine et al., SODA'20…
Routing Schemes and Distance Oracles in the Hybrid Model
Fabian Kuhn, Philipp Schneider
The model was introduced as a means for theoretical study of distributed networks that use various communication modes. Conceptually, it is a synchronous message…
Computing Shortest Paths and Diameter in the Hybrid Network Model
Fabian Kuhn, Philipp Schneider
The model, introduced in [Augustine et al., SODA '20], provides a theoretical foundation for networks that allow multiple communication modes. The model follows t…
Shortest Paths in a Hybrid Network Model
John Augustine, Kristian Hinnenthal, Fabian Kuhn +2
We introduce a communication model for hybrid networks, where nodes have access to two different communication modes: a local mode where communication is only possible between spec…