Timeline for Detecting the Appearance of a Path between a Pair of Vertices
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 3, 2018 at 17:25 | comment | added | Manfred Weis | @GerhardPaseman I was thinking, that maybe an adaptation of the disjoint set union algorithm may yield faster algorithms. But I think that problem should have already appeared elsewhere. | |
| Feb 3, 2018 at 17:02 | comment | added | Gerhard Paseman | I imagine time roughly quadratic in the number of vertices. Start by assigning a different number to each vertex. When an edge is added, if it joins two vertices with different numbers, reassign the smaller number to all vertices with the higher number, otherwise leave things alone. You are maintaining an equivalence relation of connected components. Gerhard "Not Sure Where This Leads" Paseman, 2018.02.03. | |
| Feb 3, 2018 at 16:27 | history | edited | Manfred Weis | CC BY-SA 3.0 |
removed an unnecessary graph property
|
| Feb 3, 2018 at 15:41 | history | edited | Martin Sleziak |
added top-level tag; https://meta.mathoverflow.net/questions/1457/why-are-mo-tags-formatted-as-they-are
|
|
| Feb 3, 2018 at 15:41 | history | edited | Manfred Weis | CC BY-SA 3.0 |
made a formulation more precise
|
| Feb 3, 2018 at 15:27 | history | asked | Manfred Weis | CC BY-SA 3.0 |