I was reading up algorithms for finding the minimum spanning tree(in case of weighted graphs) and for finding if a graph has a hamiltonian path(which depends on the presence of a hamiltonian cycle)...

What's the difference between a Spanning Tree and a Spanning Forest in graphs, conceptually. Also, is it possible to construct a Spanning Forest through DFS or BFS traversals? Why? How? I underst...

Suppose if all the edges have positive Weights the minimum product spanning tree can be obtained by taking the log of every edge and then apply Kruskal or Prim. But if some weights are negative, we...

Is there an algorithm to find a spanning tree of an undirected graph which minimizes the number of vertices connected to more than one edge? For example, given a 4 x 4 grid graph, we want to find ...

A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. A MBST is not necessarily a MST (minimum sp...

I have an undirected connected graph with unweighted edges. How can I build a spanning tree (the solution might not be unique) such that the sum of depths of all nodes is minimized? This is obvious...

I don't want to find all the minimum spanning trees but I want to know how many of them are there, here is the method I considered: Find one minimum spanning tree using prim's or kruskal's algori...

I came across this question from interviewstreet.com Machines have once again attacked the kingdom of Xions. The kingdom of Xions has N cities and N-1 bidirectional roads. The road network is ...