Timeline for Reverse one edge to make the most expansive strongly connected component
Current License: CC BY-SA 4.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 3, 2023 at 15:22 | history | edited | tomashauser | CC BY-SA 4.0 |
Deleted wrong reduction in O notation
|
| Jan 3, 2023 at 15:22 | comment | added | tomashauser | I guess I don't understand how to reduce the expression in $O$ if it has two parameters then. Ignore it, I'll delete it. | |
| Jan 3, 2023 at 15:19 | comment | added | tomashauser | Going through all the vertices is $V$. For every vertex, we visit its every edge. The maximum number of edges per vertex is dependent on $|E|$, therefore, asymptotically, times $E$. And everytime, we run Tarjan's algorithm in $O(V + E)$, so all of it times $(V + E)$. The problem is from a website gathering algortihm problems from an algorithms course in my university - I have no direct source. There were only this example image and two sentences describing the problem. | |
| Jan 3, 2023 at 15:09 | comment | added | Nathaniel | Also could you credit the source where you got this problem? | |
| Jan 3, 2023 at 14:54 | history | asked | tomashauser | CC BY-SA 4.0 |