Talk:Stable roommates problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated Start-class)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.


Someone should add the runtime complexity of the algorithm to find matches so I know if it's worth looking up the paper.

Runtime complexity now appears, together with a descriprion of the algorithm and an example of its execution. RobWIrving (talk) 12:55, 23 September 2010 (UTC)

Error in the example[edit]

The text explains how in Phase 2, a chain of odd length means that there is no stable pairing. On the other hand, the example ends with a stable pairing after some rotations, one of them of length 3. It's easy to check that that chain is not correct. — Preceding unsigned comment added by Davidsevilla (talkcontribs) 15:10, 29 June 2011 (UTC)


What is O(n^2)? It is written like it's common knowledge, however I'm pretty certain it's not. IMO encyclopædia should not assume previous knowledge. At least there should be a link an explanatory page. --Kebman (talk) 20:39, 6 January 2013 (UTC)

A link to Big-O Notation has since been added, which should be sufficient. An inline description isn't in line with the level this article is currently written at, at least. O2 notation is fairly common knowledge within the computer science/algorithms domain, and anyone unfamiliar with it can now click through, as with many of the concepts used here. --The Human Spellchecker (talk) 09:06, 18 November 2014 (UTC)

Rewording things a bit[edit]

I've reworded the first bit of this article in places, in order to try to make it more accessible, as some of the language was rather opaque. I have a CS degree and with it a basic understanding of set theory, and did my best to make sure that I didn't change any meaning, but I'm not an expert and not specifically familiar with the SRP, so if anyone notices any errors despite best efforts, by all means let me know (or just correct them yourself). --The Human Spellchecker (talk) 08:15, 18 November 2014 (UTC)

Software implementation[edit]

I think it useful to add links to open source software that implements algorithms to solve the stable roommates problem described in the article. To this end I suggest to add an External links section containing the following link:

Mtching (talk) 19:41, 10 December 2014 (UTC)

Possible error in the example[edit]

When we eliminate r1 = (1,4)(3,2) the element 4,6 is crossed off. Should it be? If it should, I don't see why, according to the algorithm. So perhaps it should be made clear why the 6 in the fourth row is crossed off in that step. — Preceding unsigned comment added by Zaphodbeebrox (talkcontribs) 19:32, 4 November 2016 (UTC)