#StackBounty: #algorithms #graphs #trees Cover k edges to minimize the length of the longest uncovered path in a tree

Bounty: 100

You are given a tree $Glangle V, Erangle$ and an integer $k$. The goal is to cover $k$ edges of the graph, to minimize the length of the longest uncovered path in the tree (and to return this path’s length)

Constrains: $O(nlog n)$ time and $O(n)$ space.

Now, the scheme of the algorithm is kinda obvious (from the given constrains). We need to priorities the edges and pick the highest $k$-edges (technically, we throw all edges to a priority queue and pick the first $k$)

So, I think, the keys should tell us how centric the edge is.

My first attempt was BFSing the graph from some node and BFSing again from the most distant node of the first scan.

Each node will get two values: distance from the first starting node and distance from the second starting node.

Though, I’m not sure how well this method grasp the notion of centric.

I’d be glad to hear your thoughts about the current idea or your own ideas.


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.