Re:New ‘Meow’ attack has deleted almost 4k unsecured databases
by inetknght on Sunday July 26, 2020 @07:59PM
(#23961105)
> I‘m not sure why you‘re bringing concurrency to the table.
Not using data structures that enable concurrency prevents performance improvements since modern hardware is, in general, more parallel than vertical.
My point still is that looking something up in a stack (did I visit this node?) costs O(n) time, so the BFS will degrade from O(m+n) to O(m*n+n).
To come back to the concurrency, if you can index your edges in some way, you can also store the visited flag in a separate datastracture to support concurrent access (one „flag store“ for each access).