แบบไม่มีแกนหลัก ของ ขั้นตอนวิธีโบรน-เคอร์โบสท์

รูปแบบพื้นฐานของขั้นตอนวิธีโบรน-เคอร์โบสท์ คือขั้นตอนวิธีการย้อนรอยแบบเวียนเกิด (recursive backtracking) ที่ค้นหากลุ่มพรรคพวกที่ใหญ่ที่สุดในกราฟ G โดยทั่วไป กำหนดให้มีสามเซต R P และ X แล้วมันจะทำการหากลุ่มพรรคพวกที่ใหญ่ที่สุด ที่มีทุกจุดยอดอยู่ใน R บางจุดยอดใน P และไม่มีจุดยอดใดเลยในเซต X โดยภายในการเรียกการเวียนเกิด เซต P และ X จะถูกจำกัดไว้สำหรับจุดยอดที่สร้างเป็นกลุ่มพรรคพวกเมื่อถูกรวมเข้ากับเซต R ซึ่งจุดยอดเหล่านี้เท่านั้นที่จะถูกใช้เป็นส่วนหนึ่งของข้อมูลขาออก หรือป้องกันกลุ่มพรรคพวกบางกลุ่มที่จะถูกนำไปเป็นข้อมูลขาออก

การเวียนเกิดนี้เริ่มต้นโดยกำหนดให้เซต R และ X เป็นเซตว่าง และให้ P เป็นเซตของจุดยอดของกราฟ โดยภายในการเรียกการเวียนเกิดแต่ละครั้ง จะมีการพิจารณาจุดยอดใน P ถ้าไม่มีจุดยอดใดๆเลย ก็จะให้ R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด (ในกรณีที่ X เป็นเซตว่าง) หรือให้ย้อนรอย สำหรับแต่ละจุดยอด v ที่ถูกเลือกจาก P มันจะทำการเรียกการเวียนเกิด ซึ่ง v ถูกเพิ่มเข้าไปใน R และ P กับ X ถูกจำกัดไว้สำหรับเพื่อนบ้านของ v เขียนว่า N(v) ซึ่งจะหาและรายงานส่วนเพิ่มของกลุ่มพรรคพวกของ R ซึ่งประกอบด้วย v หลังจากนั้นจะทำการย้าย v จาก P ไปยัง X และทำต่อไปเรื่อยๆ กับจุดยอดต่อไปใน P

รหัสเทียมของขั้นตอนวิธีสามารถเขียนได้ดังนี้

    BronKerbosch1(R,P,X):        ถ้า P และ X เป็นเซตว่างทั้งคู่:            รายงานว่า R เป็นกลุ่มพรรคพวกที่ใหญ่ที่สุด        สำหรับทุกๆจุดยอด v ในเซต P:            BronKerbosch1(R ⋃ {v}, P ⋂ N(v), X ⋂ N(v))            P := P \ {v}            X := X ⋃ {v}

ใกล้เคียง

ขั้นตอนวิธีแบบยุคลิด ขั้นตอนวิธีการค้นหาเพื่อนบ้านใกล้สุด 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