diff options
author | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2022-09-30 10:55:55 +0200 |
---|---|---|
committer | Jaron Kent-Dobias <jaron@kent-dobias.com> | 2022-09-30 10:55:55 +0200 |
commit | a06ff64534815cbf702a3847a19443612d307b80 (patch) | |
tree | 0b2023643f0d9d86296d4e4cbd9a683995d26230 /blossom5-v2.05.src/CHANGES.TXT | |
parent | fc1f46cd4870476d77b5ab28799f47de242e3617 (diff) | |
download | code-a06ff64534815cbf702a3847a19443612d307b80.tar.gz code-a06ff64534815cbf702a3847a19443612d307b80.tar.bz2 code-a06ff64534815cbf702a3847a19443612d307b80.zip |
Changed rbmp to use blossom algorithm.
Diffstat (limited to 'blossom5-v2.05.src/CHANGES.TXT')
-rw-r--r-- | blossom5-v2.05.src/CHANGES.TXT | 45 |
1 files changed, 45 insertions, 0 deletions
diff --git a/blossom5-v2.05.src/CHANGES.TXT b/blossom5-v2.05.src/CHANGES.TXT new file mode 100644 index 0000000..61320a6 --- /dev/null +++ b/blossom5-v2.05.src/CHANGES.TXT @@ -0,0 +1,45 @@ +Changes from version 1.0 to 2.0: + +- Replaced Fibonacci heaps with pairing heaps + (M. Fredman, R. Sedgewick, D. Sleator, R. Tarjan, Algorithmica 1(1):111-129, 1986). + Pairing heaps take less memory (namely, 2 pointers per edge less) compared to Fibonacci heaps, + and seem to be marginally faster. + + Finonacci heaps are still available - replace PQ.h with PQ-Fibonacci.h . + +- Changed data structures so that the time in SHRINK operations + is O(m log n) per augmentation (I believe). This was not the case + in version 1.0 (see footnote 5 in the MPC paper). + +I re-ran experiments corresponding to tables 1,3,4,5,9 in the paper. +The new version was marginally faster (e.g. up to 10% faster) on all examples +except for lrb744710, where it was about 3 times faster. + +Changes from version 2.0 to 2.01 (thanks to Nic Schraudolph and Dmitry Kamenetsky for useful suggestions): + +- Fixed bug in block.h (replaced "new char[] ... delete ..." with "new char[] ... delete[] ..."; +in the first case the behavious is not specified, though most compilers would compile it correctly.) + +- Removed PQ-Fibonacci.h + +- Added disclaimer about using floating point numbers + +Changes from version 2.01 to 2.02: + +- Tweaks to stop compiler warnings, + changed "delete rev_mapping" to "delete [] rev_mapping" in misc.cpp (thanks to Nic Schraudolph for suggestions) + +- Added a statement to license conditions + +Changes from version 2.02 to 2.03: + +- Fixed a bug: if the number of expands was too large (more than node_num/4) then the previous version could have crashed. +This was more likely to happen when dynamic updates were used (with multiple calls to PerfectMatching::Solve()). + +Changes from version 2.03 to 2.04: + +- Changes to make it compile under OS X and with latest gcc compilers, such as gcc 4.7.0 or 4.8.0 +(thanks to Adam Whiteside and Michael Cook for suggesting these changes). + + + |