Talk:Blossom algorithm

Description of the Blossom finding algorithm

The current description of the blossom finding algorithm doesn't refer to the matching after the step where it finds an exposed vertex. Isn't there something missing? --Lorenzo.Najt (talk) 22:12, 15 October 2019 (UTC)[reply]

Blossom definition problem

i think the definition of blossom here is slightly incorrect. a blossom is not just a cycle of size 2k+1 that contains exactly k matched edges. if it were that, then, contrary to the main theorem about blossoms, the following graph G would contain a blossom B and an augmenting path P even though after contracting B, the resulting graph G' does _not_ contain an augmenting path:

    a
    |
    b
   / \
c-d---e-f

(here the matching is M = {ab, de}, the fake blossom B = {bd, de, eb}, and the augmenting path P = {cd, de, ef}. G' after contracting B has no augmenting path.) rather, i think a blossom is also required to have connected to its base (b in this case) a simple path, vertex disjoint with B except for the base vertex, with an even number of edges, beginning with a free vertex, and alternating between unmatched and matched edges.

does anyone want to weigh in on this? --Unique-k-sat (talk) 05:49, 19 October 2009 (UTC)[reply]

yes, you are right! actually, tarjan's notes (that is where the theorem was taken from) also have some additional conditions on what blossoms qualify for the shrinking theorem. i think there are two ways how this could be fixed. do literature search and see how blossoms are defined in other sources. if they are still defined as in the wiki article, then the theorem in the main article has to be updated to state the additional conditions under which the theorem holds. if cycles have to have "stems" in order to be called blossoms, then only the definition of blossoms has to be changed to reflect this. that said, i believe the algorithm is still correct and so only either the theorem or the definition of blossoms have to be changed. 128.148.33.99 (talk) 21:44, 14 July 2010 (UTC)[reply]

One source that points this out and gives a correct version of the algorithm is Jungnickel Graphs, Networks and Algorithms. --46.253.62.108 (talk) 05:06, 7 September 2011 (UTC)[reply]

I made a correct description of the algorithm in de.WP and also provided a correct example. de:Paarung_(Graphentheorie)#Algorithmus_von_Edmonds. Not sure when or if I will find time & leisure to translate it. --goiken 17:24, 12 September 2011 (UTC)[reply]

I tried to account for the problem you reported and to reformulate the article. Hopefully it is correct now. --a3_nm (talk) 15:26, 2 June 2012 (UTC)[reply]

Blossom Diagram & Augmenting path

In the first blossom diagram, the augmenting path that is shown starts at u. Since u is adjacent to an edge in the matching, that isn't an augmenting path, right? Zabwung (talk) 00:58, 6 July 2011 (UTC)[reply]

I updated the diagrams. Does this problem still occur? --a3_nm (talk) 15:26, 2 June 2012 (UTC)[reply]

Can someone check, please?

I reverted an edit because it had changed "if and only if" to the incorrect spelling "iff".[1] Then I thought I'd better check in case the edit content was correct and just had a typo.

Daiyuda's edit: "Matching M is not maximum iff there exists an M-augmenting path in G."
My revert: "Matching M is not maximum if and only if there exists an M-augmenting path in G."
Online source:[2] "M is not a maximum matching if and only if there exists an augmenting path with respect to M."

Maybe that quote is referring to something different. But that sentence is the only match I found for "if and only if". Girlwithgreeneyes (talk) 23:04, 9 April 2012 (UTC)[reply]

"iff" is a common abbreviation in mathematics and not a typo. I think this problem is fixed now. --a3_nm (talk) 15:28, 2 June 2012 (UTC)[reply]

Okay, thanks for that. Girlwithgreeneyes (talk) 20:47, 2 June 2012 (UTC)[reply]

Restricted Reference

Reference 6 is access restricted for unregistered users. Finding a non-restricted source would be appreciated. — Preceding unsigned comment added by 190.44.82.18 (talk) 18:14, 24 November 2012 (UTC)[reply]

Ambiguity in runtime

In the section for general graphs, the runtime of Edmond's algorithm is stated to be O(V*E). The article on Edmond's algorithm however states that it needs O(V^4) time. I think the runtime with O(V*E) is achievable with a different verion of Edmond's algorithm. — Preceding unsigned comment added by 141.3.208.9 (talk) 08:01, 11 February 2016 (UTC)[reply]

Perhaps it should be made more clear, but this article is on the Blossom Algorithm, not on Edmonds's Algorithm. Edmonds discovered both, but only the latter is commonly referred to by his name. 66.134.245.203 (talk) 19:51, 9 August 2016 (UTC)[reply]

External links modified

Hello fellow Wikipedians,

I have just modified one external link on Blossom algorithm. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

Added archive https://web.archive.org/web/20081230183603/http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf to http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
If you found an error with any archives or the URLs themselves, you can fix them with this tool.

Cheers.—InternetArchiveBot (Report bug) 02:54, 22 July 2017 (UTC)[reply]