Jump to content

Karger's algorithm: Revision history

View logs for this page (view filter log)

Filter revisionsshowhide

To date:

Tag filter:

Invert selection

External tools:

For any version listed below, click on its date to view it. For more help, see Help:Page history and Help:Edit summary. (cur) = difference from current version, (prev) = difference from preceding version, m = minor edit, → = section edit, ← = automatic edit summary

curprev 19:5619:56, 12 October 2024 JJMC89 bot III talk contribs m 13,494 bytes −10 Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 undo Tag: Manual revert
curprev 02:2302:23, 12 October 2024 JJMC89 bot III talk contribs m 13,504 bytes +10 Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms undo Tag: Reverted

curprev 07:1707:17, 16 February 2024 David Eppstein talk contribs 13,494 bytes +509 random tree analysis undo

curprev 09:5509:55, 13 August 2023 OAbot talk contribs m 12,985 bytes +20 Open access bot: doi added to citation with #oabot. undo

curprev 14:3014:30, 4 April 2023 106.208.81.233 talk 12,965 bytes −550 Removed unnecessary references, fixed mistakes undo Tag: references removed
curprev 14:2414:24, 4 April 2023 106.208.81.233 talk 13,515 bytes +2 →Contraction algorithm undo

curprev 12:2612:26, 1 May 2022 93.175.28.7 talk 13,513 bytes +20 →Success probability of the contraction algorithm undo

curprev 17:2117:21, 5 February 2022 David Eppstein talk contribs 13,493 bytes −31 shorter shortdesc undo
curprev 10:2910:29, 5 February 2022 Qwerfjkl (bot) talk contribs m 13,524 bytes 0 Capitalising short description "a randomized algorithm to compute a minimum cut of a connected graph" per WP:SDFORMAT (via Bandersnatch) undo

curprev 23:3123:31, 13 January 2022 Jarble talk contribs 13,524 bytes +91 adding a short description undo

curprev 07:3707:37, 14 November 2021 Citation bot talk contribs 13,433 bytes +37 Add: s2cid. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar undo

curprev 00:4300:43, 3 October 2021 5.10.59.45 talk 13,396 bytes +5 →Contraction algorithm: remove some minor colloquialisms undo Tags: Mobile edit Mobile web edit

curprev 22:2022:20, 22 September 2021 Otg6P43MnenjqhDehK talk contribs m 13,391 bytes +4 add link to intro undo

curprev 20:2520:25, 28 July 2021 Otg6P43MnenjqhDehK talk contribs m 13,387 bytes +2 →Contraction algorithm: formatting undo

curprev 18:3718:37, 21 July 2021 Otg6P43MnenjqhDehK talk contribs 13,385 bytes +370 →Contraction algorithm: add key idea of algorithm undo

curprev 19:0619:06, 18 April 2021 Dokidaki-ylc talk contribs m 13,015 bytes +99 Improve readability when explaining the lower bound of success probability undo Tag: Visual edit

curprev 15:4115:41, 12 December 2020 Monkbot talk contribs m 12,916 bytes −33 Task 18 (cosmetic): eval 4 templates: del empty params (4×); hyphenate params (3×); undo Tag: AWB

curprev 11:4111:41, 13 May 2020 2001:b07:5d2b:d844:2c07:4a87:132b:decc talk 12,949 bytes −805 Removed section "finding all min-cuts". It was wrong. The number of min-cuts can be Omega(n^2), as mentioned in the page, yet the theorem stated that all min cunt can be found in O(polylog(n)) time undo

curprev 00:2200:22, 5 February 2020 165.91.13.39 talk 13,754 bytes −3 As mentioned in the proof we need to repeate the algorithm only $O(\ln^{2}(n))$ to get a probability of $O(\frac{1}{n})$ to find *any* minimum cut on the graph using FastCut Algorithm undo Tag: Visual edit

curprev 09:0909:09, 9 June 2019 5.8.114.249 talk 13,757 bytes +4 →Success probability of the contraction algorithm undo

curprev 21:3821:38, 9 March 2019 2610:148:1f00:3000:b09d:cbfb:a702:2a49 talk 13,753 bytes +5 →Analysis undo

curprev 20:0420:04, 25 October 2018 2a02:a317:e042:c600:44e1:ee:9612:de56 talk 13,748 bytes +5 →Improvement bound: O(n^2) means 'anything smaller than n^2', while this sentence should inform that required amount of work is 'at least c*n^2 for some constant c'. So either \Theta or \Omega should be used. Since the number of edges is no larger than n^2 I went with \Theta undo

curprev 19:3219:32, 4 December 2017 160.39.142.91 talk 13,743 bytes +1 →Repeating the contraction algorithm undo

curprev 13:0913:09, 18 April 2017 2001:638:807:20d:1d2f:e9b:f02:3de7 talk 13,742 bytes −5 →Success probability of the contraction algorithm undo

curprev 22:2422:24, 26 October 2016 128.32.38.85 talk 13,747 bytes −10 if we're looking to see where the expression becomes less than 1/2, big-O notation is not useful. undo

curprev 10:0610:06, 13 July 2016 192.16.184.34 talk 13,757 bytes −6 →Finding all min-cuts undo

curprev 04:4704:47, 21 February 2016 David Eppstein talk contribs m 13,763 bytes +37 →Success probability of the contraction algorithm: Andreas Brandstädt undo

curprev 20:2320:23, 31 January 2016 BD2412 talk contribs m 13,726 bytes −15 Fixing links to disambiguation pages, replaced: graph{{dn|date=January 2016}} → graph using AWB undo
curprev 14:4314:43, 31 January 2016 BD2412 talk contribs m 13,741 bytes +24 Graph (mathematics) is now a disambiguation link; please fix., replaced: graph → graph{{dn|{{subst:DATE}}}} using AWB undo

curprev 04:2504:25, 16 January 2016 95.60.251.201 talk 13,717 bytes +20 →The global minimum cut problem undo

curprev 02:1502:15, 22 December 2015 Michael Hardy talk contribs 13,697 bytes +2 No edit summary undo

curprev 23:0423:04, 8 December 2015 Shuaiqicao talk contribs 13,695 bytes +28 No edit summary undo Tag: Visual edit

curprev 22:0422:04, 19 November 2015 64.106.112.211 talk 13,667 bytes +2 No edit summary undo
curprev 22:0322:03, 19 November 2015 64.106.112.211 talk 13,665 bytes −2 No edit summary undo

curprev 04:2804:28, 2 October 2015 179.208.238.183 talk 13,667 bytes +2 The inequality in Karger–Stein algorithm must be non-strict, since 6 is a fixed point of t's computation function. As it was, the algorithm entered an infinite loop on certain inputs. undo

curprev 04:2104:21, 29 September 2015 171.66.209.4 talk 13,665 bytes +6 No edit summary undo

curprev 20:3720:37, 27 September 2015 Sequoia 42 talk contribs m 13,659 bytes +4 →Karger–Stein algorithm: Minor grammatical edit. undo

curprev 05:5805:58, 29 August 2015 Dexbot talk contribs m 13,655 bytes +589 Bot: Deprecating Template:Cite doi and some minor fixes undo

curprev 15:4515:45, 18 July 2015 82.140.51.111 talk 13,066 bytes +34 →The global minimum cut problem undo

curprev 09:2609:26, 18 March 2015 2406:8600:efae:7801::100d talk 13,032 bytes −88 Undid revision 651803655 by 213.27.241.137 (talk) undo
curprev 09:2209:22, 18 March 2015 2406:8600:efae:7801::100d talk 13,120 bytes −13 Undid revision 651901615 by 81.184.184.164 (talk) undo
curprev 08:5708:57, 18 March 2015 81.184.184.164 talk 13,133 bytes +13 →Finding a min-cut for each pair of vertices undo

curprev 17:1017:10, 17 March 2015 213.27.241.137 talk 13,120 bytes +88 No edit summary undo

curprev 23:0323:03, 18 February 2015 2620:0:1000:4201:5c5b:508b:db7a:c70b talk 13,032 bytes +7 →The global minimum cut problem undo

curprev 12:4312:43, 24 January 2015 F.Raab talk contribs m 13,025 bytes +4 →Improvement bound: add dense graph link undo

curprev 21:3921:39, 28 May 2014 Ecnerwala talk contribs 13,021 bytes +5 →Analysis: Fixed math. undo

curprev 19:4119:41, 10 February 2014 Zackchase talk contribs 13,016 bytes −1 No edit summary undo

curprev 20:5120:51, 9 February 2014 Zackchase talk contribs m 13,017 bytes 0 LaTeX undo
curprev 20:4420:44, 9 February 2014 Zackchase talk contribs m 13,017 bytes −24 Fixed LaTeX error undo

curprev 20:1420:14, 4 February 2014 David Eppstein talk contribs 13,041 bytes 0 Undid revision 593936492 by 171.67.87.32 (talk) no, a cut in a cycle graph is two edges, not two nodes undo

Retrieved from "https://en.wikipedia.org/wiki/Karger%27s_algorithm"