ความรู้เพิ่มเติมเกี่ยวกับขั้นตอนวิธี ของ ขั้นตอนวิธีโบรน-เคอร์โบสท์

กลุ่มพรรคพวกที่ใหญ่ที่สุด (maximal clique) คือ กลุ่มพรรคพวกที่ไม่สามารถขยายได้โดยการเพิ่มจุดยอดที่ติดกันไปอีกหนึ่งจุดหรือมากกว่านั้นอีกแล้ว ซึ่งหมายความว่าจะไม่มีกลุ่มพรรคพวกที่ปรากฏในเซตของจุดยอดของกลุ่มพรรคพวกที่ใหญ่กว่านี้อีก โดยในวงการวิทยาศาสตร์คอมพิวเตอร์ ขั้นตอนวิธีดังกล่าวเป็นปัญหาในการหากลุ่มพรรคพวกที่ใหญ่ที่สุดจัดเป็นปัญหากลุ่มพรรคพวก ปัญหากลุ่มพรรคพวกถือว่าเป็นปัญหาเอ็นพีบริบูรณ์ (NP-complete) ซึ่งเป็นกลุ่มความซับซ้อนที่ยากที่สุดในเอ็นพี ทำการควบคุมตัวแปรคงที่ได้ยากและยากที่จะประมาณค่า โดยเวลาการทำงานของขั้นตอนวิธีประเภทนี้จะใช้เวลาการทำงานเป็นแบบยกกำลัง (exponential) ซึ่งถือว่าช้ามาก

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด k ตัว ขั้นตอนวิธีของฟลอยด์-วอร์แชล ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ ขั้นตอนวิธีฮังกาเรียน ขั้นตอนวิธี ขั้นตอนวิธีของชอร์ ขั้นตอนวิธีเชิงพันธุกรรม ขั้นตอนวิธีโบรน-เคอร์โบสท์ ขั้นตอนวิธีของไดก์สตรา

แหล่งที่มา

WikiPedia: ขั้นตอนวิธีโบรน-เคอร์โบสท์ ftp://ftp-sop.inria.fr/geometrica/fcazals/papers/n... http://www.kuchaev.com/files/graph.py http://www.dfki.de/~neumann/ie-seminar/presentatio... http://www.ams.org/mathscinet-getitem?mr=0182577 //arxiv.org/abs/1006.5440 //arxiv.org/abs/1103.0318 //doi.org/10.1007%2F978-3-642-17517-6_36 //doi.org/10.1007%2FBF00991836 //doi.org/10.1007%2FBF02760024 //doi.org/10.1016%2FS0304-3975(00)00286-3