From a06ff64534815cbf702a3847a19443612d307b80 Mon Sep 17 00:00:00 2001 From: Jaron Kent-Dobias Date: Fri, 30 Sep 2022 10:55:55 +0200 Subject: Changed rbmp to use blossom algorithm. --- blossom5-v2.05.src/CHANGES.TXT | 45 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 45 insertions(+) create mode 100644 blossom5-v2.05.src/CHANGES.TXT (limited to 'blossom5-v2.05.src/CHANGES.TXT') 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). + + + -- cgit v1.2.3-70-g09d2