CS6515 Graduate Algorithms

CS6515 Graduate Algorithms

Graded Problem

You are given a weighted graph G = (V, E) with positive edge weights. Give a linear time (O(E] + [VI)) algorithm to decide if an input edge e – (u, v) is part of some MST of G or not. You should describe your algorithm in words (a list is okay); no pseudocode. Explain why it is correct and justify its running time.

Let G be an undirected graph, and lets and t be distinct vertices of G. Each edge in G is assigned one of two colors, white or gold.
You may assume that the color of an edge, C(e), is
available to you in constant time.
(a.) Design an algorithm that determines if there is a path from s to t with edges of only one color (that is, a path containing either white edges only or gold edges only).
(b.) Design an algorithm that determines if there is a path from s to t such that all white edges appear before all gold edges in the path. Paths of a single color are OK, but no gold edge can appear before any white edge.