Articles Posted by admin

1. Let G be an undirected graph with n vertices and m edges. Describe an O(n+m)- time algorithm for traversing each edge of G exactly once in each direction.2. Implement an algorithm that returns a...

Say that an n-vertex directed acyclic graph  is compact if there is some way of numbering the vertices of  with the integers from 0 to n−1 such that  contains the edge (i, j) if and only if i...

1. Show that if all the weights in a connected weighted graph G are distinct, then there is exactly one minimum spanning tree for G.2. An old MST method, called Baruvka’s algorithm, works as follows...

Write a method, components(G), for undirected graph G, that returns a dictionary mapping each vertex to an integer that serves as an identifier for its connected component. That is, two vertices...

An independent set of an undirected graph G = (V,E) is a subset I of V such that no two vertices in I are adjacent. That is, if u and v are in I, then (u,v) is not in E. A maximal independent set M...