umsh1ume's blog

How do I select maximum vertices in a graph in this case:-?
By umsh1ume, history, 7 years ago, In English

I need to select maximum vertices in a graph such that the distance between any two selected vertices is less than the given limit? distance between adjacent nodes is 1. Input n,d meaning number of nodes and the limit d, n-1 lines follows denoting edges. Example 6 5 2 1 2 3 4 2 1 6 5 6

Output 5 As all 5 vertices can be selected within the range d

  • Vote: I like it
  • -6
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Seems, your graph is a tree, because you wrote there n-1 edges. If so, there exists simple algo O(n^2), for every node run BFS no longer distance than d. calculate number of nodes.

source

And, I belive that, there must exists linear solution.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3 1

    1 2

    2 3

    in this case your output is 3 but the answer is 2

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks, yea, I didn't read problem carefully.

      There required distance for each vertex in the set must less than limit d.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if n<=20 , then you can solve it by dp + bitmask

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

CAN YOU SHARE LINK TO PROBLEM ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If this graph is a tree, there exists O(N^2) solution.

In the graph for every pair of vertexes exist single path.

Think that, if we build solution, there exist a pair of vertexes where distance is maximum, select middle of these vertexes, for selected vertex, distance from it to any other vertexes in the set less or equal (1+d)/2.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

dp[i][j][k] -- number of nodes in subtree rooted at node i , using jth of its child , upto a depth of of k.. For every node , we will have the number of nodes in each child subtree upto different heights of different nodes..

→ Reply