DAA - ปกเวอร์เท็กซ์
จุดยอดปกของกราฟที่ไม่ได้บอกทิศทาง G = (V, E) เป็นส่วนย่อยของจุดยอด V' ⊆ V เช่นนั้นถ้าขอบ (u, v) เป็นขอบของ Gแล้วอย่างใดอย่างหนึ่ง u ใน V หรือ v ใน V' หรือทั้งคู่.
ค้นหาจุดยอดครอบคลุมขนาดสูงสุดในกราฟที่ไม่ได้กำหนดทิศทาง จุดยอดที่ดีที่สุดนี้เป็นเวอร์ชันการเพิ่มประสิทธิภาพของปัญหา NP-complete อย่างไรก็ตามไม่ยากเกินไปที่จะหาจุดยอด - ฝาปิดที่ใกล้เคียงที่สุด
APPROX-VERTEX_COVER (G: Graph) c ← { } E' ← E[G]
while E' is not empty do
Let (u, v) be an arbitrary edge of E' c ← c U {u, v}
Remove from E' every edge incident on either u or v
return c
ตัวอย่าง
ชุดขอบของกราฟที่กำหนดคือ -
{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,8),(3,5),(8,5)}
ตอนนี้เราเริ่มต้นด้วยการเลือกขอบโดยพลการ (1,6) เรากำจัดขอบทั้งหมดซึ่งอาจเกิดขึ้นกับจุดยอด 1 หรือ 6 และเราเพิ่มขอบ (1,6) เพื่อปิดทับ
ในขั้นตอนต่อไปเราได้เลือกขอบอื่น (2,3) แบบสุ่ม
ตอนนี้เราเลือกขอบอื่น (4,7)
เราเลือกขอบอื่น (8,5)
ดังนั้นจุดยอดปกของกราฟนี้คือ {1,2,4,5}
การวิเคราะห์
มันง่ายที่จะเห็นว่าเวลาทำงานของอัลกอริทึมนี้คืออะไร O(V + E)โดยใช้ adjacency list เพื่อแสดง E'.