Is it possible to find a common MST between two graphs?
Difference between en1 and en2, changed 1 character(s)
Given two weighted, undirected graphs on $n$ nodes $G_1$ and $G_2$, is it possible to efficiently find a tree on these $n$ nodes that is an MST of both $G_1$ and $G_2$?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English shsh 2026-04-23 22:10:08 2 Tiny change: 'tively. \n- Note t' -> 'tively. \n\n- Note t'
en5 English shsh 2026-04-23 09:32:59 192
en4 English shsh 2026-04-23 09:31:03 1913 Tiny change: ' possible.' -> ' possible.\n\nHere's a problem that uses this idea: [problem:1054G]'
en3 English shsh 2025-07-20 09:35:23 8
en2 English shsh 2025-07-20 09:34:43 1 Tiny change: ' both $G_1 and $G_2$' -> ' both $G_1$ and $G_2$'
en1 English shsh 2025-07-20 09:34:01 222 Initial revision (published)