ปัญหาที่เกี่ยวข้อง ของ ปัญหาการแต่งงานที่มีเสถียรภาพ

การจับคู่กราฟสองส่วน (Bipartite matching) กล่าวคือ ปัญหาการแต่งงานที่มีเสถียรภาพนี้เป็นตัวอย่างหนึ่งของการจับคู่กราฟสองส่วนโดยทั่วไปในเรื่องของทฤษฏีกราฟ
ปัญหาการจัดตารางช่วงเวลา (Interval scheduling problem) เป็นตัวอย่างหนึ่งของขั้นตอนวิธีแบบละโมภ
การจัดตาราช่วงเวลาแบบถ่วงน้ำหนัก (Weighted interval scheduling) ซึ่งเป็นตัวอย่างหนึ่งของปัญหาการจัดตารางช่วงเวลา โดยให้มีหอประชุมขนาดใหญ่ และมีการจัดกิจกรรมต่าง ๆ ที่จะต้องจัดตารางเวลาในการใช้หอประชุมแห่งนี้ โดยกิจกรรมต่าง ๆ นั้นมีเวลาที่เริ่มของกิจกรม และเวลาที่จบของกิจกรรมนั้น ๆ ซึ่งปัญหานี้เกี่ยวข้องกันโดยที่เราจะต้องจัดการตารางเวลาให้มีกิจกรรมจัดขึ้นมากที่สุดในช่วงเวลาที่กำหนด
เซตอิสระ (Independent Set) โดยให้มีกราฟ G ที่มีปมเป็น V และเส้นเชื่อมเป็น E โดยเราจะสามารถบอกได้ว่า เซตของปม S จะเป็นเซตอิสระ ถ้าไม่มีสองปอมใด ๆ ที่มีเส้นเชื่อมซึ่งกันและกัน ซึ่งการหาเซตอิสระที่ใหญ่ที่สุดในกราฟ G จะเป็นส่วนหนึ่งของปัญหาเอ็นพีบริบูรณ์ (NP-Complete)
การแข่งขันหาทำเลที่ตั้งสิ่งอำนวยความสะดวก (Competitive Facility Location) เป็นเกมที่มีผู้เล่นตั้งแต่ 2 คนขึ้นไป ทำการเดินและเลือกที่ตั้งที่ทำให้ตนมีคะแนนมากที่สุด โดยกลยุทธ์ที่จะสามารถทำให้ชนะในเกมนี้คือการเลือกจุดเริ่มต้นของที่ตั้ง และการตัดสินใจในการเลือกเดินของผู้เล่นในตาก่อนหน้านี้ ซึ่งเกมนี้เป็นตัวอย่างหนึ่งของปัญหาพีเสปซบริบูรณ์

แหล่งที่มา

WikiPedia: ปัญหาการแต่งงานที่มีเสถียรภาพ http://sephlietz.com/gale-shapley/ http://www.cs.columbia.edu/~evs/intro/stable/Stabl... http://www.cs.columbia.edu/~evs/intro/stable/Stabl... http://www1.cs.columbia.edu/~evs/intro/stable/writ... http://www.columbia.edu/~js1353/pubs/tst-ms01.pdf http://www.academic.marist.edu/~jzbv/algorithms/Th... http://www.csee.wvu.edu/~ksmani/courses/fa01/rando... http://www.jstor.org/pss/3008420 http://kevindriscoll.org/wiki/Algorithm_design http://rosettacode.org/wiki/Stable_marriage_proble...