ผลต่างระหว่างรุ่นของ "VC-SNDP:spider decomposition"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
แถว 7: แถว 7:
 
== Decomposition ==
 
== Decomposition ==
  
Chuzhoy และ Khanna ได้ใช้ spider decomposition ในการพิสูจน์ approximation algorithm สำหรับ ss-k-sndp  ในที่นี้เราจะใช้ decomposition ที่ weak กว่าของ Chekuri และ Korula
+
Chuzhoy และ Khanna ได้ใช้ spider decomposition ในการพิสูจน์ approximation algorithm สำหรับ ss-k-sndp  อย่างไรก็ตามในที่นี้เราจะใช้ decomposition ที่ weak กว่าของ Chekuri และ Korula
  
 
Chekuri-Korula แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ ''k''-element connected, มีสับกราฟ ''H'' ของ ''G'' ที่สามารถ partition เป็น spiders ที่
 
Chekuri-Korula แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ ''k''-element connected, มีสับกราฟ ''H'' ของ ''G'' ที่สามารถ partition เป็น spiders ที่

รุ่นแก้ไขเมื่อ 06:13, 24 กุมภาพันธ์ 2552

This page describes spider decompositions and the approach of Chuzhoy Khanna and Chekuri and Korula in tackling the single-source k sndp.

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

Spider คือ tree ที่มีโหนดที่มีดีกรีมากกว่าสองไม่เกิน 1 จุดยอด ถ้ามี vertex ดังกล่าว จะเรียกว่าเป็น head ถ้าไม่มี spider จะเป็น path และจะสามารถเรียกโหนดใดเป็น head ก็ได้; เรียกจุดยอดที่ไม่ใช่ leaf และ head ว่า intermediate vertex, เรียก leaf ว่า foot, เรียก path จาก head ไป leaf ว่า leg

Decomposition

Chuzhoy และ Khanna ได้ใช้ spider decomposition ในการพิสูจน์ approximation algorithm สำหรับ ss-k-sndp อย่างไรก็ตามในที่นี้เราจะใช้ decomposition ที่ weak กว่าของ Chekuri และ Korula

Chekuri-Korula แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ k-element connected, มีสับกราฟ H ของ G ที่สามารถ partition เป็น spiders ที่

  1. ทุก ๆ leaf เป็น black vertex
  2. ทุก ๆ black vertex เป็น leg ของ k spiders พอดี
  3. ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้) และสำหรับกรณีที่ spider มี white vertex เป็น head จะต้องมี leg อย่างน้อย 2 legs

ด้านล่างแสดงตัวอย่างของ spiders

Spiders.png

Approximating SS-k-VC-SNDP

Reduction lemma

Proof of the spider decomposition with the reduction lemma