VC-SNDP:spider decomposition

This page describes spider decompositions and the approach of CK and ChK.

ให้กราฟ $G=(V,E)$ เซตของ terminals $T$ และจำนวนเต็มบวก $k$ เรียกโหนดใน $T$ เป็น black vertices, นอกจากนั้นเป็น white vertices.

Spider คือ

• tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด (ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex)
• ทุก ๆ leaf เป็น black vertex เรียกว่า foot. แต่ละกิ่งเรียกว่า leg
• ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้)

ตัวอย่างของ spiders