Timeline for Enumerating the elements of cartesian products in ascending order of $\|\cdot\|_1$ norm
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 20, 2022 at 20:20 | comment | added | David Eppstein | Dijkstra is also superior in space even if you want to list all pairs. (Also, sorting might take different time than what you state, if you use an integer sorting method; see en.wikipedia.org/wiki/Integer_sorting) | |
| Jul 19, 2022 at 10:47 | comment | added | Manfred Weis | If "a general-purpose sorting algorithm" sorts the elements of $X\times Y$, it costs $O(2n^2\log n)$ time for sorting them; sorting the individual lists is $O(2n\log n)$ the size of the "Dijkstra-algorithm heap" is $O(n)$ so that an update operation is $O(\log n)$ and $O(n^2)$ updates are made indicating that both methods are in $O(n^2\log n)$. The situation in which the Dijkstra algorithm is superior is when listing all pairs isn't the objective, e.g. in branch-and-bound situations. | |
| Jul 19, 2022 at 6:29 | history | answered | David Eppstein | CC BY-SA 4.0 |