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

ประวัติ

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

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

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

บันทึก

Paper: Minimum-Latency Broadcast Scheduling in Wireless Ad Hoc Networks.

ที่มา INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE (2007), pp. 733-739. ของ Huang, S.C.-H. Peng-Jun Wan Xiaohua Jia Hongwei Du Weiping Shang

Problem

An instance of Minimum-Latency Broadcast Scheduling consists of an undirected graph $G=(V,E)$ representing the communication topology and a distinguished node $s\in V$ as the source of the broadcast. For any subset $U$ of $V$, denote by $Inf(U)$ the set of nodes in $V\setminus U$ each of which has exactly one neighbor in $U$. Then a broadcast schedule of latency $l$ is a sequence $<U_{1},U_{2},\cdots ,U_{l}>$ satisfying that

(1)$U_{1}=\{s\}$.

(2)$U_{i}\subseteq \cup _{j=1}^{i-1}Inf(U_{j})$ for each $2\leq i\leq l$.

(3)$V\setminus \{s\}\subseteq \cup _{j=1}^{l}Inf(U_{j})$.

The problem MLBS seeks a broadcast schedule of the smallest latency.

แต่สนใจ MLBS ใน unit-disk graphs G(V,E) ที่จะมี edge เชื่อมระหว่าง 2 nodesก็ต่อเมื่อ ระยะทาง(euclidean distance)ระหว่างสองโหนดนั้นไม่เกิน 1

บันทึก

เข้าใจว่า

อัลกอริทึมจะสร้าง BFS tree$T$ของ $G$ rooted at $s$ แล้วคำนวณหาความลึกของทุกๆ nodes ใน tree จากนั้นในแต่ละชั้น $i$ จะหา maximal independent set $U_{i}$ จะเรียก node พวกนี้ว่าเป็น dominators ส่วน node ที่เป็น parents ของ dominators ใน T เรียกว่า connectors เวลาที่ส่งข้อมูลจาก s ก็จะเริ่มส่งไป dominator->connector->dominator ไปเรื่อยๆ

ในแต่ละชั้นนั้ independent set $U$ of UDG $G$ จะถูกแบ่งเป็น 12 2-IS of $G$ ซึ่งจะมองเป็น proper node coloring of $G^{2}$ ซึ่งแต่ละ subset ใน partition จะสอดคล้องกับสี หนึ่งสี

ทีนี้ส่วนที่น่าสนใจจะเป็นในแต่ละชั้นจะส่งข้อมูลกันอย่างไร โดยที่ไม่ชนกัน ซึ่งปัญหานี้แปลงไปเป็นปัญหา coloring ได้