Log In
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Sep 2019
  1. Satbir

    567 Points

  2. Bikram

    566 Points


    348 Points

  4. Vimal Patel

    87 Points

  5. Shaik Masthan

    38 Points


    14 Points

  7. sekhar_1621

    13 Points

  8. OgbeborBeatrice

    13 Points

  9. RAMYA.F

    9 Points

  10. vkw1111

    9 Points

0 votes

1) Suppose you’re a consultant for the networking company CluNet, and they have the following problem. The network that they’re currently working on is modelled by a connected graph G=(V,E) with n nodes. Each edge e is a fibre-optic cable that is owned by one of the companies –named X and Y and leashed to CluNet.

Their plan is to choose a spanning tree T of G and upgrade the links corresponding to the edges of T. Their business relations people have already concluded an agreement with the companies, X and Y stipulating a number k so that in the tree T that is chosen, k of the edges will be owned by X and n-k-1 of the edges will be owned by Y.

Give a polynomial time algorithm, that takes G, with each edge labelled X or Y, and either (i) returns a spanning tree with exactly k edges labelled X, or (ii) reports correctly that no such tree exists.

in Algorithms 7 points 10 views

Please log in or register to answer this question.