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$$$?
Is it possible to quickly find a common MST between two graphs?
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$$$?
| Rev. | Lang. | By | When | Δ | Comment | |
|---|---|---|---|---|---|---|
| en6 |
|
shsh | 2026-04-23 22:10:08 | 2 | Tiny change: 'tively. \n- Note t' -> 'tively. \n\n- Note t' | |
| en5 |
|
shsh | 2026-04-23 09:32:59 | 192 | ||
| en4 |
|
shsh | 2026-04-23 09:31:03 | 1913 | Tiny change: ' possible.' -> ' possible.\n\nHere's a problem that uses this idea: [problem:1054G]' | |
| en3 |
|
shsh | 2025-07-20 09:35:23 | 8 | ||
| en2 |
|
shsh | 2025-07-20 09:34:43 | 1 | Tiny change: ' both $G_1 and $G_2$' -> ' both $G_1$ and $G_2$' | |
| en1 |
|
shsh | 2025-07-20 09:34:01 | 222 | Initial revision (published) |
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
