GATE CSE
First time here? Checkout the FAQ!
x
0 votes
33 views

A college prepares its timetable by grouping courses in slots A, B, C, . . . All courses in a slot meet at the same time, and courses in different slots have disjoint timings. Course registration has been completed and the administration now knows which students are registered for each course. If the same student is registered for two courses, the courses must be assigned different slots. The administration is trying to compute the minimum number of slots required to prepare the timetable.
The administration decides to model this as a graph where the nodes are the courses and edges represent pairs of courses with an overlapping audience. In this setting, the graph theoretic question to be answered is:

  1. Find a spanning tree with minimum number of edges.
asked in Graph Theory by Veteran (73.3k points)   | 33 views

Please log in or register to answer this question.

Related questions

Top Users Jan 2017
  1. Debashish Deka

    7508 Points

  2. Habibkhan

    4716 Points

  3. Vijay Thakur

    4368 Points

  4. sudsho

    4316 Points

  5. saurabh rai

    4170 Points

  6. santhoshdevulapally

    3436 Points

  7. Arjun

    3432 Points

  8. Bikram

    3240 Points

  9. GateSet

    3202 Points

  10. Sushant Gokhale

    3042 Points

Monthly Topper: Rs. 500 gift card

18,898 questions
23,865 answers
51,932 comments
20,186 users