Is it possible to find a common MST between two graphs?

Revision en1, by shsh, 2025-07-20 09:34:01

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

Unable to parse markup [type=CF_MATHJAX]

?
Tags mst, spanning tree, tree

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)