Talk:Blossom algorithm: Difference between revisions

Revision as of 21:44, 14 July 2010

Latest revision as of 23:44, 8 March 2024

(21 intermediate revisions by 15 users not shown)

Line 1:

{{mathsWikiProject ratingbanner shell|class=StartC|priorityvital=Lowyes|field1=discrete}}

{{WikiProject Mathematics|priority=Low}}

}}

== 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? --[[User:Lorenzo.Najt|Lorenzo.Najt]] ([[User talk:Lorenzo.Najt|talk]]) 22:12, 15 October 2019 (UTC)

== 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,

Line 23 ⟶ 32:

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.

[[Special:Contributions/128.148.33.99|128.148.33.99]] ([[User talk:128.148.33.99|talk]]) 21:44, 14 July 2010 (UTC)

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

::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. --[[user:0g1o2i3k4e5n6|goiken]] 17:24, 12 September 2011 (UTC)

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

==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? [[User:Zabwung|Zabwung]] ([[User talk:Zabwung|talk]]) 00:58, 6 July 2011 (UTC)

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

== Can someone check, please? ==

I reverted an edit because it had changed "if and only if" to the incorrect spelling "iff".[http://en.wikipedia.org/w/index.php?title=Edmonds%27s_matching_algorithm&diff=prev&oldid=486519279] 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:[http://www.cs.berkeley.edu/~karp/greatalgo/lecture05.pdf] "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". [[User:Girlwithgreeneyes|Girlwithgreeneyes]] ([[User talk:Girlwithgreeneyes|talk]]) 23:04, 9 April 2012 (UTC)

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

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

==Restricted Reference==

Reference 6 is access restricted for unregistered users. Finding a non-restricted source would be appreciated. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/190.44.82.18|190.44.82.18]] ([[User talk:190.44.82.18|talk]]) 18:14, 24 November 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== 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. <small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/141.3.208.9|141.3.208.9]] ([[User talk:141.3.208.9|talk]]) 08:01, 11 February 2016 (UTC)</small><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

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.

[[Special:Contributions/66.134.245.203|66.134.245.203]] ([[User talk:66.134.245.203|talk]]) 19:51, 9 August 2016 (UTC)

== External links modified ==

Hello fellow Wikipedians,

I have just modified one external link on [[Blossom algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=791725425 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|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.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 02:54, 22 July 2017 (UTC)