Timeline for Girth of Undirected Graph with Positive Integer Weights
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2017 at 2:58 | comment | added | D.W.♦ | @neutron-byte, that actually is a cycle -- it's just not a simple cycle. | |
| Sep 17, 2017 at 15:12 | comment | added | neutron-byte | There is a problem. Consider the graph consisting of only two vertices connected with a single undirected (as stated in question) edge with weight 1. Obviously, the graph contains no cycle. But Floyd-Warshall yields $d[v][v] = 2$ for this vertex... I think your algorithm does only work in directed graphs. | |
| Sep 17, 2017 at 3:53 | comment | added | D.W.♦ | @neutron-byte, see revised answer for a proof. | |
| Sep 17, 2017 at 3:53 | history | edited | D.W.♦ | CC BY-SA 3.0 |
added 521 characters in body
|
| Sep 16, 2017 at 22:20 | comment | added | neutron-byte | Why does this work? It sounds plausible but I don't see how to prove it. | |
| Sep 16, 2017 at 22:07 | history | answered | D.W.♦ | CC BY-SA 3.0 |