News for hackers. Stuff that matters.
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by jrp on Sunday April 11, 2010 @07:56PM (#1257974)
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by tjr on Sunday April 11, 2010 @08:46PM (#1258041)
As if that could stop Knuth...
Re:Donald Knuth making an Earthshaking Announcement June 30 ... by faragon on Monday April 12, 2010 @02:07AM (#1258537)
But what if you:

1) Create a list of pairs for the N nodes, N^2/2 elements: O(N^2). This point complexity could be ignored, as an initialization phase, as precomputed data for next step. In addition, many lists of hamiltonian subpaths could be added for trading memory for time complexity (not big deal, just linear speedup).

2) Dynamic-size (hamiltonian path subset) algebraic mergesort (avoiding evaluation, in order to avoid O(N!)): O(NlogN), or maybe O(N^2), or O(N^2logN)

That could give you time complexity between O(N^2) and O(N^2logN). I tried something for the point (2), but obviously I had no success on compensating the combinatorial explosion with simplification/remapping. Possible or not, it is neverending and cheap fun.