ผลต่างระหว่างรุ่นของ "จักริน ชวชาติ"
Chung (คุย | มีส่วนร่วม) (สร้างหน้าใหม่: = ประวัติ = '''ชื่อ:''' จักริน ชวชาติ = หัวข้องานวิจัย = == Degree Limiting Minim...) |
Chung (คุย | มีส่วนร่วม) |
||
| แถว 10: | แถว 10: | ||
Given a metric length function <math>\ell</math> over a set <math>V</math> of <math>n</math> nodes, and a degree-bound <math>B_v</math> for each <math>v\in V</math>, the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree <math>T</math> of <math>G</math> of minimum diameter such that each node <math>v</math> has degree at most <math>B_v</math> in <math>T</math>. | Given a metric length function <math>\ell</math> over a set <math>V</math> of <math>n</math> nodes, and a degree-bound <math>B_v</math> for each <math>v\in V</math>, the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree <math>T</math> of <math>G</math> of minimum diameter such that each node <math>v</math> has degree at most <math>B_v</math> in <math>T</math>. | ||
=== เอกสารอ้างอิง === | === เอกสารอ้างอิง === | ||
| − | + | Shi, S. Y.; Turner, J. S. & Waldvogel, M. Dimensioning server access bandwidth and multicast routing in overlay networks In 11th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’01), 2001, 83-92 | |
| + | |||
| + | Frederickson, G. N.; Hecht, M. S. & Kim, C. E. Approximation Algorithms for Some Routing Problems SIAM Journal on Computing, SIAM, 1978, 7, 178-193 | ||
| + | |||
| + | Könemann, J.; Levin, A. & Sinha, A. Approximating the degree-bounded minimum diameter spanning tree problem Algorithmica, Springer, 2003, 109-121 | ||
| + | |||
= บันทึก = | = บันทึก = | ||
รุ่นแก้ไขเมื่อ 08:36, 16 มีนาคม 2552
เนื้อหา
ประวัติ
ชื่อ: จักริน ชวชาติ
หัวข้องานวิจัย
Degree Limiting Minimum Diameter Tree Problem
เป็นปัญหา Network design มีกราฟ ต้องการหา spanning tree โดยมี objective ที่สนใจอยู่ 2 อย่าง ได้แก่ low diameter และ degree ของแต่ละ nodeไม่เกินดีกรีที่ node นั้นรับได้ ปัญหานี้สามารถนำไปประยุกต์ใช้เกี่ยวกับงาน peer to peer streaming ได้คือต้องการให้มี delay น้อย(สัมพันธ์กับ diameter) และการ assign งานไม่เกินที่แต่ละ node รับได้(สอดคล้องกับ degree)
Problem Definition
Given a metric length function over a set of nodes, and a degree-bound for each , the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree of of minimum diameter such that each node has degree at most in .
เอกสารอ้างอิง
Shi, S. Y.; Turner, J. S. & Waldvogel, M. Dimensioning server access bandwidth and multicast routing in overlay networks In 11th International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV’01), 2001, 83-92
Frederickson, G. N.; Hecht, M. S. & Kim, C. E. Approximation Algorithms for Some Routing Problems SIAM Journal on Computing, SIAM, 1978, 7, 178-193
Könemann, J.; Levin, A. & Sinha, A. Approximating the degree-bounded minimum diameter spanning tree problem Algorithmica, Springer, 2003, 109-121
