ผลต่างระหว่างรุ่นของ "VC-SNDP:spider decomposition"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 1: | แถว 1: | ||
| − | This page describes '''spider decompositions''' and the approach of | + | This page describes '''spider decompositions''' and the approach of Chuzhoy Khanna and Chekuri and Korula in tackling the single-source k sndp. |
ให้กราฟ <math>G=(V,E)</math> เซตของ terminals ''T'' และจำนวนเต็มบวก <math>k</math> เรียกโหนดใน ''T'' ว่าเป็น black vertices, นอกจากนั้นเป็น white vertices. | ให้กราฟ <math>G=(V,E)</math> เซตของ terminals ''T'' และจำนวนเต็มบวก <math>k</math> เรียกโหนดใน ''T'' ว่าเป็น black vertices, นอกจากนั้นเป็น white vertices. | ||
| แถว 7: | แถว 7: | ||
== Decomposition == | == Decomposition == | ||
| − | + | Chuzhoy และ Khanna ได้ใช้ spider decomposition ในการพิสูจน์ approximation algorithm สำหรับ ss-k-sndp ในที่นี้เราจะใช้ decomposition ที่ weak กว่าของ Chekuri และ Korula | |
| + | |||
| + | Chekuri-Korula แสดงว่า ให้กราฟ G ที่ทุก ๆ คู่ของจุดยอดสีดำ ''k''-element connected, มีสับกราฟ ''H'' ของ ''G'' ที่สามารถ partition เป็น spiders ที่ | ||
# ทุก ๆ leaf เป็น black vertex | # ทุก ๆ leaf เป็น black vertex | ||
# ทุก ๆ black vertex เป็น leg ของ ''k'' spiders พอดี | # ทุก ๆ black vertex เป็น leg ของ ''k'' spiders พอดี | ||
รุ่นแก้ไขเมื่อ 06:11, 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 ที่
- ทุก ๆ leaf เป็น black vertex
- ทุก ๆ black vertex เป็น leg ของ k spiders พอดี
- ทุก ๆ intermediate vertex เป็น white vertex (สังเกตว่า head เป็น black vertex ได้) และสำหรับกรณีที่ spider มี white vertex เป็น head จะต้องมี leg อย่างน้อย 2 legs
ด้านล่างแสดงตัวอย่างของ spiders
