Bundit:2-paths routing

ปัญหา

รับกราฟ $G=(V,E)$ ต้องการหา routing table ที่มีขนาดเล็ก??? และ วิธีการ route ที่ไม่ซับซ้อน???

งานที่ทำมาแล้ว

ใช้ Gomory-Hu tree (cut-equivalent tree) ในการหา routing table

• งานวิจัยวันที่ 15 กุมภาพันธ์ พ.ศ.2550
  • สิ่งที่ผิด
    1. edge ใน gomory-hu tree มันไม่ได้โยงกลับไปหา edge ในกราฟได้ง่าย
    2. โหนดและ edge ใน tree มันไม่ได้เป็น edge ที่เชื่อมกับโหนดนั้น เช่น มี edge (u,v) มันหมายความว่า cut ของกราฟ ระหว่าง set Vu และ Vv ( Vu แทนเซตของโหนดใน subtree ที่อยู่ด้านเดียวกับ u เมื่อลบ (u,v)) มีขนาดอย่างน้อย 2 แต่ edge เหล่านี้ไม่จำเป็นต้องต่อกับ u หรือ v
    3. edge ใน cut พวกนี้ ไม่จำเป็นต้อง disjoint