จักริน ชวชาติ

ประวัติ

ชื่อ: จักริน ชวชาติ

หัวข้องานวิจัย

Degree Limiting Minimum Diameter Tree Problem

เป็นปัญหา Network design มีกราฟ $G=(V,E)$ ต้องการหา spanning tree $T$ โดยมี objective ที่สนใจอยู่ 2 อย่าง ได้แก่ low diameter และ degree ของแต่ละ nodeไม่เกินดีกรีที่ node นั้นรับได้ ปัญหานี้สามารถนำไปประยุกต์ใช้เกี่ยวกับงาน peer to peer streaming ได้คือต้องการให้มี delay น้อย(สัมพันธ์กับ diameter) และการ assign งานไม่เกินที่แต่ละ node รับได้(สอดคล้องกับ degree)

Problem Definition

Given a metric length function $\ell$ over a set $V$ of $n$ nodes, and a degree-bound $B_{v}$ for each $v\in V$, the Degree-Limiting Minimum-Diameter Spanning Tree Problem (DLDST) is to find a spanning tree $T$ of $G$ of minimum diameter such that each node $v$ has degree at most $B_{v}$ in $T$.

เอกสารอ้างอิง

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