Skip to main content
Share Your Experience: Take the 2024 Developer Survey

Questions tagged [spanning-trees]

The spanning tree of a connected undirected graph G is a tree having all the vertices and some number of edges of G.

Filter by
Sorted by
Tagged with
0 votes
1 answer
30 views

Robust maximum weight forests with weights on edges

In an undirected weighted graph with edge weights, the task is to find a spanning tree T. An adversary will delete two edges (not necessarily from T), and subsequently, we can add an edge (excluding ...
Toyllo's user avatar
  • 1
6 votes
1 answer
905 views

Can every spanning tree result from a depth-first search?

A graph can have multiple spanning trees and the spanning tree resulting from a depth-first search depends on the order in which edges are processed. Can every possible spanning tree of a given graph ...
schuelermine's user avatar
0 votes
1 answer
40 views

An "edge-spanning-tree" of minimum height

Given any connected undirected graph, we can convert it into a tree by "detaching" some edges from one of their endpoints. For example, consider the graph with the following edges: $$ (1) ~~~...
Erel Segal-Halevi's user avatar
0 votes
0 answers
16 views

Prove that the a bottleneck of path P is maximal

As the title says, the question is about finding the maximal bottleneck edge in path P. Bottleneck of a path P in an undirected graph G = (V,E) is defined to be the weight of the edge with minimal ...
Salty Champ's user avatar
0 votes
2 answers
110 views

Distinct edge weights assumption in second best MST algorithms only replacing an edge in MST

In a CP-algorithms wiki Second Best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor: Let  $T$  be the Minimum Spanning Tree of a graph $G$ . It can be observed, that the second best ...
Kenneth Kho's user avatar
2 votes
0 answers
63 views

Borůvka's step in linear time

I am trying to understand this Expected linear time MST algorithm, and I have a problem in the implementation of the Borůvka's step. My problem is with the removal of duplicate edges between merged ...
Nathaniel's user avatar
  • 15.7k
0 votes
0 answers
44 views

Find spanning tree by removing heaviest weight

I need to design the following algorithm: Given an undirected, simple, and connected graph $G=(V,E)$ and some positive weight function $w$. The algorithm needs to scan the edges from the heavier edge ...
Joe's user avatar
  • 1
1 vote
1 answer
46 views

Is deciding whether a graph admits two vertex-disjoint spanning trees of bounded size difference NP-hard?

I'd like to decide whether, given a connected graph $G = (V, E)$ and an integer $k$ as input, $G$ admits two vertex-disjoint subgraphs $T_1 = (V_1, E_1)$ and $T_2 = (V_2, E_2)$ such that $T_1$ and $...
J. Schmidt's user avatar
1 vote
1 answer
284 views

Finding existence(or non existence) of spanning tree with a specific degree on a specific vertex

Given an undirected graph $G=(V,E)$, and vertex $v\in V$ and a number $k\in \mathbb{N}$, find an algorithm to find whether there exists a spanning tree of $G$ in which $v$ satisfies $d(v)=k$ I've ...
Aishgadol's user avatar
  • 355
1 vote
1 answer
32 views

What is the time complexity of the EMST problem in 3D space

We have an unstructured cloud of $N$ points in 3D space. What is known about the complexity of building the Euclidean Minimum Spanning Tree of the points ? The tree is made of $N-1$ edges and can be ...
user avatar
1 vote
1 answer
66 views

safe edge theorem proof clarification

I found the following proof for the theorem that states "A light edge that crosses a cut that respects A is safe for A": See: https://www2.hawaii.edu/~janst/311_f19/Notes/Topic-17.html ...
Tryer outer's user avatar
1 vote
1 answer
64 views

Recreate a spanning tree in a grid graph given vertex descriptions

Let's assume I have graph above with spanning tree pointed out by blue edges. Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1. Vertex at position (4,2) (...
Looft's user avatar
  • 175
4 votes
2 answers
1k views

Spanning tree - minimum difference between smallest and largest weight

I am given an undirected, weighted graph $G$, on its base I have to create a spanning tree with such a property that the difference between the largest edge weight and the smallest edge weight is the ...
PK96's user avatar
  • 71
0 votes
0 answers
350 views

Wrong Solution for `Spanning tree with chosen leaves` problem

Suppose that we're given a connected, undirected graph $G = (V, E)$ with edge weights $w_e$ and a subset of vertices $U \subset V$. We want to find the lightest spanning tree in which the nodes of $U$ ...
Robert's user avatar
  • 1
2 votes
0 answers
40 views

The Roskind-Tarjan Algorithm

I am going through the paper https://pubsonline.informs.org/doi/abs/10.1287/moor.10.4.701 which is A Note on Finding Minimum-Cost Edge-Disjoint Spanning Trees and the authors are James Roskind and ...
Ash Ketchum's user avatar
2 votes
0 answers
64 views

Edmond's theorem for k-disjoint arborescences in digraphs

Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs if a finite digraph is $k$ edge-connected from a vertex r for ...
Ash Ketchum's user avatar
2 votes
1 answer
217 views

Spanning tree that maximizes all-pairs bandwidth => Maximum spanning tree?

Let $G = (V, E)$ be a weighted, undirected graph, with $f: E \to \mathbb{R}$ its weight function. Given a path $P = (e_1, \dots, e_k)$, we call $\operatorname{bwd}(P) = \min_{1 \le i \le k} f(e_i)$ ...
Federico Lebrón's user avatar
2 votes
1 answer
276 views

Prove finding a spanning tree with no more than 50 leaves is NP-hard

This is a homework question. Consider the problem of finding if an undirected graph $G$ can have a spanning tree with no more than 50 leaves. Is this problem NP-hard? I think it is and I'm trying to ...
Rob32409's user avatar
  • 115
1 vote
1 answer
108 views

Linear deterministic algorithm for finding spanning tree T with minimal maximum edge

Given an undirected connected graph $G = (V, E)$ with weights $w : $E → $R$$^+$, define for a spanning tree T the value $λ$(T) = $max_e$∈$T${w(e)} (the maximal edge weight in T ). I need to find a ...
Omri's user avatar
  • 11
2 votes
2 answers
1k views

How does Dijkstra's problem 1 (tree of minimal total length) work and what does it do?

In Dijkstra's original paper, he talks about two problems related to graphs. The second one is the problem of finding the shortest path between two nodes, which is what is most commonly meant by ...
Jarne Renders's user avatar
2 votes
3 answers
2k views

Algorithm to get any spanning tree not necessarily a minimum spanning tree

Is there an algorithm to find a spanning tree. I know that there are $n^{n-2}$ of them and we have algorithms to find a minimum spanning tree. But what if I just want any spanning tree? It doesn't ...
heretoinfinity's user avatar
2 votes
2 answers
527 views

Is the inverse of MST cut property true? Why?

If we partition the nodes of a graph into sets A and B, there is an edge e of weight larger than any other edge crossing the cut between A and B, e would never be in the minimum spanning tree?
user624's user avatar
  • 57
2 votes
1 answer
216 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

CLRS problem 23-4 part c gives an algorithm that may or may not compute a minimum spanning tree. Given some connected undirected graph G, we have ...
xdavidliu's user avatar
  • 858
1 vote
1 answer
232 views

Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

I have a vertex-weighted undirected graph $(V,E)$ with root vertices $R = {r1, ..., rn}$. I need to find the subset $V'⊂V$ such that $R⊂V'$, $N[V']=V$, $∀v'∈V '[∃r∈R ($path($r', v'$)$)]$ that ...
J. Vroegindeweij's user avatar
0 votes
1 answer
216 views

Undirected graph whose BFS and DFS trees have roots of degree 2

Draw a graph on $5$ vertices that satisfies all of the following conditions: $G$ is an undirected connected graph. For every node $v∈V$, in the spanning tree received by BFS($v$), $\deg v=2$. For ...
Lee's user avatar
  • 167
0 votes
1 answer
309 views

Number of spanning arborescences with a specific root in a directed graph

I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example: where there are 5 spanning arborescences. Note that there is an edge ...
Edward's user avatar
  • 131
0 votes
1 answer
379 views

Finding minimum possible cost of road network between cities with distance from capital condition

I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E). Characteristics of the graph: Each city is connected to the rest of the graph Each city ...
restler's user avatar
-1 votes
1 answer
255 views

maximum spanning tree in a complete graph

Given a complete graph how do I find maximum weight spanning tree. where $weight(u, v) = \sum_{i=1}^{k} |w_{i,u} - w_{i,v}|$ assuming $k \lt 7$ and $n \le 500000$. $n$ number of nodes $weight(u,v)$ ...
difficult_problem's user avatar
-1 votes
1 answer
95 views

Prove following statement about Kruskal Algorithm

Let G be undirected graph, G=(V,E), and all edge weights are distinct. Consider an edge e=(u,v)∈E that wasn't included in the solution obtained from applying Kruskal Algorithm to G. Prove that this ...
Kate Austen's user avatar
2 votes
0 answers
73 views

Total weight of all spanning trees

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
abhi01nat's user avatar
  • 141
1 vote
1 answer
522 views

Minimum spanning tree of multi directed graph

I have problem of inferring a rooted tree out of a connected simple graph. The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of ...
Edward's user avatar
  • 131
0 votes
3 answers
61 views

Variation to spanning tree called Group Spanning Tree

Suppose we have a complete graph, with say 100 nodes. We divide the nodes in the graph into groups, for example 10 nodes in each group, identified by color. We want to obtain a minimum spanning tree ...
meowcat's user avatar
4 votes
1 answer
60 views

Count bridging edges in a family of two component forests

I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two ...
blue's user avatar
  • 141
8 votes
0 answers
199 views

MST with possibly minimal diameter

I am working with some research problem connected loosely to TSP which requires to find the Minimum Spanning Tree of a fully connected, weighted graph, where all the weights are positive and the graph ...
I_Really_Want_To_Heal_Myself's user avatar
1 vote
2 answers
2k views

Graph with exactly 2 Minimum Spanning Trees

Say that a graph, $G = (V, E)$ has 2 minimum spanning trees (MSTs). Given this condition stipulated, prove that any cycle formed by all the edges in both the MSTs (i.e., the union of the edges in ...
user avatar
3 votes
1 answer
195 views

how to generate all spanning trees from one spanning tree

If I have one spanning tree from a connected and undirected graph, how can I generate all other spanning trees of this graph by modifying this spanning tree one edge at a time? All intermediates must ...
Tommy Hebert's user avatar
3 votes
1 answer
566 views

Kirchhoff's Spanning Tree Algorithm

Recently I have studied Kirchhoff's spanning tree algorithm to count the number of spanning trees of a graph, which has the following steps: Build an adjacency matrix Replace the diagonal entries ...
Turing101's user avatar
  • 1,200
0 votes
1 answer
27 views

Finding most likely tree over a semilattice

If I am not mistaken, then a semilattice defines a finite set of trees, for example spanning trees. Now assume that each semilattice edge is annotated with a transition probability. In addition, let'...
Radio Controlled's user avatar
2 votes
1 answer
194 views

Number of spanning trees in undirected simple graph

What is the number of spanning trees in an undirected simple graph? My attempt: Let $m$ be the number of edges in a simple graph, and let $n$ be the number of vertices. Then number of spanning ...
Nascimento de Cos's user avatar
0 votes
1 answer
46 views

Name for Turning DAG into redundant tree

I am looking for a term: How is the tree called that you can obtain from a DAG by going top-down and appending all visited nodes to a tree, thereby copying nodes from the DAG into multiple occurences ...
Radio Controlled's user avatar
1 vote
1 answer
252 views

Average branching factor of an undirected graph

I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every ...
ABu's user avatar
  • 529
0 votes
2 answers
214 views

First time visited nodes form a spanning tree that has a same number of edges in both BFS and DFS

I am trying to state, whether the statement is true: During a DFS/BFS, first time visited nodes form a spanning tree, that has the same number of edges whether you use DFS or BFS. Is it true? What I ...
james F.'s user avatar
  • 111
1 vote
1 answer
682 views

Do the minimum spanning trees of a graph have the same number of edges with a given weight?

I'm asking about the answer here: Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight? I didn't understand the best answer here Choose edge $e \in ...
Arjun Hegde's user avatar
3 votes
1 answer
2k views

Is maximum-leaves spanning tree np-complete?

How can we show that a maximum-leaves spanning tree is NP-complete? what other np-complete problem we can use as our reduction base? (maximum-leaves spanning tree: does G have a spanning tree with at ...
mellodi's user avatar
  • 33
0 votes
0 answers
21 views

Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?

The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem. Imagine a row of commands: ...
Anony Pony's user avatar
1 vote
1 answer
112 views

The role of the root switch after Spanning Tree Protocol has established a tree network in a LAN?

In Spanning Tree Protocol, a root switch is selected at first, and then somehow, the shortest path from each other switch to the root is obtained. Thus we established a tree network. My questions ...
Mengfan Ma's user avatar
0 votes
2 answers
1k views

Minimum Distance Spanning Tree Dijkstra

I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below: MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)} Is my ...
CObject's user avatar
  • 35
2 votes
1 answer
8k views

DFS & BFS Spanning Trees

I want to construct a DFS and a BFS spanning trees for the graph below. The root is node a. At each step the next edge to be traversed should be the cheapest one. DFS: My understanding that to the ...
CObject's user avatar
  • 35
25 votes
7 answers
6k views

Do any two spanning trees of a simple graph always have some common edges?

I tried few cases and found any two spanning tree of a simple graph has some common edges. I mean I couldn't find any counter example so far. But I couldn't prove or disprove this either. How to ...
Mr. Sigma.'s user avatar
  • 1,303
2 votes
2 answers
1k views

Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance) $\alpha$ denotes the start and end vertex of ...
Sebastian Nielsen's user avatar