Edge-disjoint spanning trees and depth-first search

By Robert Endre Tarjan. 1976

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

1. Jihong Park
2. Anis Elgabli
3. Medhi Bennis
4. Sumudu Samarakoon
5. Vaneet Aggarwal
6. Amrit Singh Bedi
7. Steven Euijong Whang
8. Hector Garcia-Molina

Citations in the corpus

• GADMM: Fast and Communication Efficient Framework for Distributed Machine Learning (2019, methodology): “Even though an approach like spanning tree can be used to create such a graph (Tarjan, 1976; Kruskal, 1956), coming up with the most communication efficient graph is a NP complete problem (being a generalization of traveling salesman problem) and is beyond the scope of this paper.”
• Joint Entity Resolution (2012, methodology): “Identifying the strongly connected components in G (Step 1) can be done in O(|V |+ |E|) time using existing method such as Tarjan’s algorithm [24].”