Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

How to find all the edges shared by all diameters of a tree?

Revision en1, by pabloskimg, 2019-09-09 23:00:56

Given a tree, I need to find all the edges that are shared by all diameters of that tree. In other words, let D be the length of the longest path in the tree and P be the set of all paths in the tree with length = D. I need to find the intersection of the edges shared by all paths in P. How can I do that? Please do not just mention the algorithm, I would appreciate if you can share the theoretical justification of why it works too (links to lectures or any resources are also very appreciated).

Thank you very much.

Tags #diameter, #trees, #graph theory

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English pabloskimg 2019-09-10 01:48:33 424
en2 English pabloskimg 2019-09-10 01:10:28 123
en1 English pabloskimg 2019-09-09 23:00:56 582 Initial revision (published)