อั ลกอริทึม Recursive Largest First ( RLF ) เป็นฮิวริสติกสำหรับปัญหาการระบายสีกราฟNP-hard โดยได้รับการเสนอครั้งแรกโดย Frank Leighton ในปี 1979 ^{[ 1 ]}

อัลกอริทึม RLF กำหนดสีให้กับจุดยอดของกราฟโดยการสร้างกลุ่มสีแต่ละกลุ่มทีละกลุ่ม โดยจะทำเช่นนั้นด้วยการระบุกลุ่มจุดยอดอิสระที่ใหญ่ที่สุดในกราฟ กำหนดสีเดียวกันให้กับจุดยอดเหล่านั้น แล้วจึงลบจุดยอดเหล่านั้นออกจากกราฟ การกระทำเหล่านี้จะถูกทำซ้ำกับกราฟย่อยที่เหลืออยู่จนกว่าจะไม่มีจุดยอดเหลืออยู่

เพื่อสร้างโซลูชันคุณภาพสูง (โซลูชันที่ใช้สีน้อย) อัลกอริทึม RLF ใช้กฎฮิวริสติกเฉพาะเพื่อพยายามระบุชุดอิสระที่มี "คุณภาพดี" ฮิวริสติกเหล่านี้ทำให้อัลกอริทึม RLF แม่นยำสำหรับกราฟแบบไบพาร์ไทต์วงจรและวงล้อ^{[ 2 ]} อย่างไรก็ตาม โดยทั่วไปแล้ว อัลกอริทึมนี้เป็นการประมาณค่าและอาจส่งคืนโซลูชันที่ใช้สีมากกว่า จำนวนสีของ กราฟ

อัลกอริทึมนี้สามารถอธิบายได้ด้วยสามขั้นตอนต่อไปนี้ ในตอนท้ายของกระบวนการนี้จะได้การแบ่งกลุ่มของจุดยอดที่แสดงถึงการระบายสีที่เป็นไปได้ของ กราฟ${\displaystyle {\mathcal {S}}}$${\displaystyle |{\mathcal {S}}|}$${\displaystyle G}$

1. ให้เป็นโซลูชันว่างเปล่า และให้เป็นกราฟที่เราต้องการระบายสี ซึ่งประกอบด้วยเซตของจุดยอดและเซตของเส้นเชื่อม${\displaystyle {\mathcal {S}}=\emptyset }$${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$
2. ระบุเซตอิสระที่ใหญ่ที่สุด โดยทำดังนี้: ${\displaystyle S\subseteq V}$
   1. จุดยอดแรกที่จะเพิ่มเข้าไปควรเป็นจุดยอดที่มีจำนวนเพื่อนบ้านมากที่สุด${\displaystyle S}$${\displaystyle G}$
   2. จุดยอดถัดไปที่จะเพิ่มเข้าไปในควรเลือกจุดยอดที่ (ก) ไม่ติดกับจุดยอดใดๆ ใน ในปัจจุบันและ (ข) มีจำนวนเพื่อนบ้านที่ติดกับจุดยอดใน มากที่สุดหากเงื่อนไข (ข) ทั้งสองข้อเท่ากัน สามารถเลือกจุดยอดที่มีจำนวนเพื่อนบ้านที่ไม่ติดกับ ใน น้อยที่สุดมาตัดสินได้จะเพิ่มจุดยอดเข้าไปในลักษณะนี้เรื่อยๆ จนกว่าจะไม่สามารถเพิ่มจุดยอดได้อีกต่อไป${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$
3. ตอนนี้กำหนดและลบจุดยอดของจากถ้ายังคงมีจุดยอดอยู่ ให้กลับไปที่ขั้นตอนที่ 2 มิฉะนั้นให้สิ้นสุด${\displaystyle {\mathcal {S}}={\mathcal {S}}\cup \{S\}}$${\displaystyle S}$${\displaystyle G}$${\displaystyle G}$

พิจารณากราฟที่แสดงทางด้านขวา นี่คือกราฟวงล้อดังนั้น RLF จะระบายสีกราฟได้อย่างเหมาะสมที่สุด การดำเนินการตามอัลกอริทึมจะส่งผลให้จุดยอดถูกเลือกและระบายสีตามลำดับต่อไปนี้: ${\displaystyle G=(V,E)}$

1. จุดยอด(สี 1)${\displaystyle g}$
2. จุดยอด, , และจากนั้น(สี 2)${\displaystyle a}$${\displaystyle c}$${\displaystyle e}$
3. จุดยอด, , และจากนั้น(สี 3)${\displaystyle b}$${\displaystyle d}$${\displaystyle f}$

ซึ่งจะได้สารละลายสามสีสุดท้าย ${\displaystyle {\mathcal {S}}=\{\{g\},\{a,c,e\},\{b,d,f\}\}}$

ให้เป็นจำนวนจุดยอดในกราฟ และให้เป็นจำนวนขอบ โดยใช้สัญกรณ์บิ๊กโอในเอกสารต้นฉบับของเขา Leighton ระบุว่าความซับซ้อนของ RLF คือ; อย่างไรก็ตาม สามารถปรับปรุงให้ดีขึ้นได้ ค่าใช้จ่ายส่วนใหญ่ของอัลกอริทึมนี้เกิดจากขั้นตอนที่ 2 ซึ่งการเลือกจุดยอดจะทำตามกฎฮิวริสติกที่กล่าวไว้ข้างต้น อันที่จริง ทุกครั้งที่มีการเลือกจุดยอดเพื่อเพิ่มลงในเซตอิสระข้อมูลเกี่ยวกับเพื่อนบ้านจะต้องถูกคำนวณใหม่สำหรับแต่ละจุดยอดที่ยังไม่ได้ระบายสี การคำนวณเหล่านี้สามารถทำได้ในเวลา ซึ่งหมายความว่าความซับซ้อนโดยรวมของ RLF คือ^{[ 2 ]}${\displaystyle n}$${\displaystyle m}$${\displaystyle {\คณิตศาสตร์ {O}}(n^{3})}$${\displaystyle S}$${\displaystyle {\คณิตศาสตร์ {O}}(m)}$${\displaystyle {\คณิตศาสตร์ {O}}(mn)}$

หากฮิวริสติกของขั้นตอนที่ 2 ถูกแทนที่ด้วยการเลือกแบบสุ่ม ความซับซ้อนของอัลกอริทึมนี้จะลดลงเหลือ; อย่างไรก็ตาม อัลกอริทึมที่ได้มักจะให้ผลลัพธ์ที่มีคุณภาพต่ำกว่าเมื่อเทียบกับ RLF ^{[ 2 ]}นอกจากนี้ยังจะไม่แม่นยำสำหรับกราฟ แบบ สองส่วนวงจรและ วงล้ออีก ด้วย ${\displaystyle {\คณิตศาสตร์ {O}}(n+m)}$

จากการเปรียบเทียบเชิงประจักษ์โดย Lewis ในปี 2021 พบว่า RLF สามารถสร้างการระบายสีจุดยอดได้ดีกว่าฮิวริสติกทางเลือกอื่นๆ เช่นอัลกอริทึมแบบโลภและ อัลกอริทึม DSaturบนกราฟแบบสุ่มอย่างมีนัยสำคัญ อย่างไรก็ตาม พบว่าเวลาในการรันไทม์ของ RLF สูงกว่าทางเลือกอื่นๆ เนื่องจากมีความซับซ้อนโดยรวมสูงกว่า^{[ 2 ]}${\displaystyle {\คณิตศาสตร์ {O}}(n+m)}$${\displaystyle {\คณิตศาสตร์ {O}}((n+m)\lg n)}$

• GColคือไลบรารี Python แบบโอเพนซอร์สสำหรับระบายสีกราฟโดยใช้ RLF (Real-Time Load)
• ชุด อัลกอริธึมการระบายสีกราฟประสิทธิภาพสูง (เขียนด้วยภาษา C++) ที่ใช้ในหนังสือ "A Guide to Graph Colouring: Algorithms and Applications" (Springer International Publishers, 2021)