Stack Overflow
Stack Overflow

Questions tagged [spanning-tree]

A spanning tree in an connected, undirected graph is a subgraph that includes all vertices, is a tree and is connected.

106 questions
35
votes
2 answers

How is a minimum bottleneck spanning tree different from a minimum spanning tree?

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 spanning tree). Please give an example where these…
Nikunj Banka
  • 11,117
  • 16
  • 74
  • 112
25
votes
3 answers

Spanning tree which minimizes the number of vertices connected to multiple edges?

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 spanning tree like that on the left (which has 7…
user200783
  • 13,722
  • 12
  • 69
  • 135
14
votes
4 answers

Difference between Hamiltonian path and ST

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). I got everything messed up. So whats the…
letsc
  • 2,075
  • 5
  • 24
  • 43
12
votes
2 answers

Spanning Tree VS. Spanning Forest

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 understand the Spanning Tree, but I couldn't find any clear…
Nima Salami
  • 123
  • 1
  • 1
  • 5
9
votes
2 answers

How to find total number of minimum spanning trees in a graph?

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 algorithm and then find the weights of all the spanning…
2147483647
  • 1,177
  • 3
  • 13
  • 33
8
votes
2 answers

Minimum product spanning tree with negative weights

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 can't apply this procedure. since we need to…
AJAY HAYAGREEVE
  • 168
  • 10
8
votes
1 answer

Finding a spanning tree that minimizes sum of nodes' depths

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 obviously not finding the minimum spanning tree, as the…
klkh
  • 265
  • 1
  • 2
  • 11
6
votes
6 answers

Bidirectional spanning tree

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 such that there is a unique path between any pair…
user1374210
  • 63
  • 1
  • 4
5
votes
1 answer

Max weight euclidean spanning tree

A maximum spanning tree can be found by running kruskal's algorithm(just changing the edges function and considering the max weight edges first). I am interested in finding the max weight euclidean spanning tree. Does there exist a better…
user1448750
4
votes
1 answer

Algorithm for minimum diameter spanning tree

Given a undirected and connected graph G, find a spanning tree whose diameter is the minimum.
Rambo
  • 741
  • 1
  • 8
  • 12
4
votes
1 answer

Finding a spanning tree using exactly k red edges in a graph with edges colored by red/blue in linear time

Given a graph G with red and blue edges and a constant K, devise a deterministic, linear time algorithm that finds a spanning tree of G with exactly K red edges (or returns False if such a spanning tree does not exist). What we have done so far: Let…
Rachel Bernouli
  • 225
  • 2
  • 9
3
votes
2 answers

How to generate and plot all spanning trees?

I have a toy graph g, then I have found the number of spanning trees by cofactor of the Laplacian. The number is 11. library(igraph) set.seed(2) n <- 5 # n=5 m <- 6 # m=6 g <- erdos.renyi.game(n, p.or.m=m, type="gnm" , directed=FALSE,…
Nick
  • 1,086
  • 7
  • 21
3
votes
2 answers

spanning tree with exactly k colored edges

I have a connected, undirected graph with edges that are each either black or white, and an integer k. I'm trying to write an algorithm that tells whether or not a spanning tree exists with exactly k black edges (doesn't necessarily have to find the…
Rupert
  • 31
  • 1
  • 2
3
votes
1 answer

Polynomial time algorithm for minimum variance spanning tree

Lets define the variance of a graph as the variance of its edges' weights. The task I am trying to solve is designing an algorithm which given a graph G will construct a spanning tree T with minimum variance. I am having a hard time getting the…
A.F.K.
  • 69
  • 7
3
votes
2 answers

Edge disjoint spanning trees

I have come across a question based on spanning tree i.e : what is the upper bound on the number of edge disjoint spanning trees in a complete graph of n vertices? (a) n (b) n-1 (c) [n/2] (d) [n/3] what do we mean by edge disjoint spanning…
POOJA GUPTA
  • 2,295
  • 7
  • 32
  • 60
1
2 3 4 5 6 7 8