lshw: *-cpu description: CPU product: Intel(R) Core(TM)2 Duo CPU T5550 @ 1.83GHz vendor: Intel Corp. physical id: 4 bus info: cpu@0 version: Intel(R) Core(TM)2 Duo CPU T5550 @ 1.83GHz serial: PSN12345678901234567 slot: Socket 478 size: 1826MHz capacity: 1837MHz width: 64 bits clock: 167MHz capabilities: fpu fpu_exception wp vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx x86-64 constant_tsc arch_perfmon pebs bts rep_good nopl aperfmperf pni dtes64 monitor ds_cpl est tm2 ssse3 cx16 xtpr pdcm lahf_lm cpufreq *-cache:0 description: L1 cache physical id: 5 slot: L1-Cache size: 64KiB capacity: 64KiB capabilities: internal write-back instruction *-cache:1 description: L2 cache physical id: 6 slot: L2-Cache size: 2MiB capacity: 2MiB capabilities: internal write-back unified *-memory description: System Memory physical id: 19 slot: System board or motherboard size: 2GiB *-bank:0 description: DIMM DDR Synchronous product: PartNum0 vendor: Manufacturer0 physical id: 0 serial: SerNum0 slot: DIMM0 size: 1GiB width: 64 bits *-bank:1 description: DIMM DDR Synchronous product: PartNum1 vendor: Manufacturer1 physical id: 1 serial: SerNum1 slot: DIMM1 size: 1GiB width: 64 bits ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 20000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.00439501 General matching 0.00581098 Push-relabel matching 0.0270121 Pull-relabel matching 0.0195651 Preflow 0.0704179 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 20000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.007617 General matching 0.00865293 Push-relabel matching 0.0281398 Pull-relabel matching 0.022635 Preflow 0.084631 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 200000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0196722 General matching 0.0496941 Push-relabel matching 0.0402629 Pull-relabel matching 0.023067 Preflow 0.084374 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 200000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 200000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0173001 General matching 0.039665 Push-relabel matching 0.0378501 Pull-relabel matching 0.0209558 Preflow 0.083463 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 5000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.140268 General matching 0.757882 Push-relabel matching 1.03231 Pull-relabel matching 0.191497 Preflow 2.43836 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 5000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 5000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.14244 General matching 0.748836 Push-relabel matching 1.01037 Pull-relabel matching 0.177195 Preflow 2.43532 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 50000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.00485301 General matching 0.0332901 Push-relabel matching 0.034101 Pull-relabel matching 1.61998 Preflow 0.0291169 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 50000 -density 100000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 50000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.00491309 General matching 0.0323601 Push-relabel matching 0.0341032 Pull-relabel matching 1.64628 Preflow 0.02914 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 10000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0106671 General matching 0.0234542 Push-relabel matching 0.598726 Pull-relabel matching 0.0256259 Preflow 0.441146 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 10000 -density 100000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 10000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.00621796 General matching 0.02387 Push-relabel matching 0.013314 Pull-relabel matching 0.0249431 Preflow 0.420767 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0959971 General matching 0.0536282 Push-relabel matching 0.564037 Pull-relabel matching 0.409038 Preflow 2.87165 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 100000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0964329 General matching 0.0539811 Push-relabel matching 0.577723 Pull-relabel matching 0.498138 Preflow 2.9425 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 500000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.300473 General matching 0.659012 Push-relabel matching 0.285235 Pull-relabel matching 0.716639 Preflow 0.659159 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 500000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 500000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.290675 General matching 0.799577 Push-relabel matching 0.278713 Pull-relabel matching 0.673765 Preflow 0.644327 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.078588 General matching 0.0866389 Push-relabel matching 1.07703 Pull-relabel matching 1.05606 Preflow 13.6679 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 100000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 100000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.0867798 General matching 0.0857451 Push-relabel matching 1.14464 Pull-relabel matching 1.1683 Preflow 15.3508 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 500000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.738178 General matching 6.79053 Push-relabel matching 0.629064 Pull-relabel matching 2.00591 Preflow 1.51949 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 500000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 500000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 1.06521 General matching 3.61031 Push-relabel matching 1.86594 Pull-relabel matching 0.550163 Preflow 3.38694 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.946682 General matching 1.92071 Push-relabel matching 1.72593 Pull-relabel matching 0.501604 Preflow 3.05918 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 1000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.816804 General matching 2.1141 Push-relabel matching 0.720706 Pull-relabel matching 0.558198 Preflow 1.57464 ------------------------------------------------------------------ ./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 200000 red, 100000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.301091 General matching 0.394658 Push-relabel matching 51.6478 Pull-relabel matching 0.429368 Preflow 5.04168 ------------------------------------------------------------------ ./unweighted-bp-gen -red 200000 -blue 100000 -density 1000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 200000 red, 100000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.436297 General matching 0.398948 Push-relabel matching 51.8427 Pull-relabel matching 0.433397 Preflow 5.25675 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 200000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.10732 General matching 6.44808 Push-relabel matching 0.620226 Pull-relabel matching 202.475 Preflow 0.631016 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 200000 -density 1000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 200000 blue nodes, and 1000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.106734 General matching 7.05392 Push-relabel matching 0.619569 Pull-relabel matching 203.459 Preflow 0.631564 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 5000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.92472 General matching 2.1869 Push-relabel matching 2.08447 Pull-relabel matching 0.823065 Preflow 3.89623 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 5000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 5000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.768868 General matching 2.34836 Push-relabel matching 2.04811 Pull-relabel matching 0.856978 Preflow 3.81936 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 10000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 1.35792 General matching 3.95055 Push-relabel matching 4.13391 Pull-relabel matching 1.34968 Preflow 7.61363 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 100000 -density 10000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 100000 blue nodes, and 10000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 1.40444 General matching 3.9244 Push-relabel matching 4.12933 Pull-relabel matching 1.37161 Preflow 7.68012 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 20000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.622058 General matching 3.5884 Push-relabel matching 4.81846 Pull-relabel matching 0.722273 Preflow 15.3129 ------------------------------------------------------------------ ./unweighted-bp-gen -red 10000 -blue 10000 -density 20000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 10000 red, 10000 blue nodes, and 20000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.559423 General matching 3.56505 Push-relabel matching 4.82065 Pull-relabel matching 0.719321 Preflow 14.6463 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 10000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.865783 General matching 2.86391 Push-relabel matching 3.51891 Pull-relabel matching 0.884747 Preflow 6.92598 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 10000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 10000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 0.864196 General matching 2.91178 Push-relabel matching 3.55595 Pull-relabel matching 0.880587 Preflow 6.95554 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 2.3675 General matching 8.98925 Push-relabel matching 11.8477 Pull-relabel matching 2.6124 Preflow 27.0935 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 50000 -density 30000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 50000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 2.5767 General matching 9.19034 Push-relabel matching 12.1031 Pull-relabel matching 2.72674 Preflow 27.1568 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 100000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 3.72626 General matching 13.7599 Push-relabel matching 13.8212 Pull-relabel matching 3.76943 Preflow 14.8385 ------------------------------------------------------------------ ./unweighted-bp-gen -red 50000 -blue 100000 -density 30000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 50000 red, 100000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 3.77606 General matching 14.0525 Push-relabel matching 14.0126 Pull-relabel matching 3.80314 Preflow 14.8287 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 1 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 50000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 1.56758 General matching 4.84758 Push-relabel matching 0.927193 Pull-relabel matching 1.58256 Preflow 41.4949 ------------------------------------------------------------------ ./unweighted-bp-gen -red 100000 -blue 50000 -density 30000000 -seed 10 Benchmarking in unweighted case, using a bipartite graph with 100000 red, 50000 blue nodes, and 30000000 edges. -------------------------------------------------------- Algorithm used Time Hopcroft-Karp 1.59166 General matching 4.75917 Push-relabel matching 0.924 Pull-relabel matching 1.58148 Preflow 41.5419