1 citations · 1 across the 6 of their papers we have counts for
6 papers
The Steiner Shortest Path Tree Problem
Omer Asher, Yefim Dinitz, Shlomi Dolev +2
We introduce and study a novel problem of computing a shortest path tree with a minimum number of non-terminals. It can be viewed as an (unweighted) Steiner Shortest Path Tree (SSP…
On Existence of Must-Include Paths and Cycles in Undirected Graphs
Yefim Dinitz, Solomon Eyal Shimony
Given an undirected graph and vertices , we study finding whether there exists a simple path from to such that . As a sub-pro…
Partially Disjoint k Shortest Paths
Yefim Dinitz, Shlomi Dolev, Manish Kumar +1
A solution of the shortest paths problem may output paths that are identical up to a single edge. On the other hand, a solution of the independent shortest paths problem co…
Polynomial Time -Shortest Multi-Criteria Prioritized and All-Criteria-Disjoint Paths
Yefim Dinitz, Shlomi Dolev, Manish Kumar
The shortest secure path (routing) problem in communication networks has to deal with multiple attack layers e.g., man-in-the-middle, eavesdropping, packet injection, packet insert…
Local Deal-Agreement Based Monotonic Distributed Algorithms for Load Balancing in General Graphs
Yefim Dinitz, Shlomi Dolev, Manish Kumar
In computer networks, participants may cooperate in processing tasks, so that loads are balanced among them. We present local distributed algorithms that (repeatedly) use local imb…
Shallow, Low, and Light Trees, and Tight Lower Bounds for Euclidean Spanners
Yefim Dinitz, Michael Elkin, Shay Solomon
We show that for every -point metric space there exists a spanning tree with unweighted diameter and weight . Moreover, the…