Timeline for Sorting a binary matrix diagonal in polynomial time while preserving rows
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 13, 2010 at 0:10 | answer | added | Tracy Hall | timeline score: 4 | |
| Aug 12, 2010 at 7:42 | history | edited | Charles Matthews | CC BY-SA 2.5 |
upper case title
|
| Aug 12, 2010 at 4:07 | comment | added | Gilead | Incidentally the algorithm proposed by Duff has a worst case complexity of $O(n\tau)$ where $n$ is the order of the matrix, and $\tau$ is the number of nonzeros, though it is mentioned that in practice, the algorithm achieves $O(n) + O(\tau)$. The paper also cites another algorithm by Hopkroft and Karp that has a worst case complexity of $O(\sqrt{n}\tau)$. | |
| Aug 12, 2010 at 1:40 | comment | added | Gilead | This sounds an awful lot like the Maximum Traversal problem. This is dealt with in this classic paper by Duff (portal.acm.org/citation.cfm?id=355963). There is also a piece of FORTRAN code called mc21a in the Harwell libraries for doing this efficiently. (hsl.rl.ac.uk/specs/mc21.pdf) | |
| Aug 11, 2010 at 19:11 | history | edited | Will Jagy |
edited tags
|
|
| Aug 11, 2010 at 18:15 | answer | added | Aaron Meyerowitz | timeline score: 3 | |
| Aug 11, 2010 at 17:56 | history | asked | Tristan | CC BY-SA 2.5 |