ผลต่างระหว่างรุ่นของ "จักริน ชวชาติ"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
(jMkhODePyBGFu)
แถว 1: แถว 1:
= ประวัติ =
+
You have shed a ray of snushine into the forum. Thanks!
'''ชื่อ:''' จักริน ชวชาติ
 
 
 
= หัวข้องานวิจัย =
 
 
 
== Degree Limiting Minimum Diameter Tree Problem ==
 
เป็นปัญหา Network design มีกราฟ <math>G=(V,E)</math> ต้องการหา spanning tree <math>T</math> โดยมี objective ที่สนใจอยู่ 2 อย่าง ได้แก่ low diameter และ degree ของแต่ละ nodeไม่เกินดีกรีที่ node นั้นรับได้ ปัญหานี้สามารถนำไปประยุกต์ใช้เกี่ยวกับงาน peer to peer streaming ได้คือต้องการให้มี delay น้อย(สัมพันธ์กับ diameter) และการ assign งานไม่เกินที่แต่ละ node รับได้(สอดคล้องกับ degree)
 
 
 
=== Problem Definition ===
 
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
 
 
 
= บันทึก =
 
 
 
=='''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 <math>G=(V,E)</math> representing the communication topology and a distinguished node <math>s\in V</math> as the source of the broadcast.  
 
For any subset <math>U</math> of <math>V</math>, denote by <math>Inf(U)</math> the set of nodes in <math>V\setminus U</math> each of which has exactly one neighbor in <math>U</math>. Then a broadcast schedule of latency <math>l</math> is a sequence <math><U_1, U_2,\cdots , U_l></math> satisfying that
 
 
 
(1)<math>U_1 =\{s\}</math>.
 
 
 
(2)<math>U_i\subseteq \cup_{j=1}^{i-1}Inf(U_j)</math> for each <math>2\leq i\leq l</math>.
 
 
 
(3)<math>V\setminus \{s\}\subseteq \cup_{j=1}^{l}Inf(U_j)</math>.
 
 
 
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<math> T</math>ของ <math>G</math> rooted at <math>s</math> แล้วคำนวณหาความลึกของทุกๆ nodes ใน tree จากนั้นในแต่ละชั้น <math>i</math> จะหา maximal independent set <math>U_i</math> จะเรียก node พวกนี้ว่าเป็น dominators ส่วน node ที่เป็น parents ของ dominators ใน T เรียกว่า connectors เวลาที่ส่งข้อมูลจาก s ก็จะเริ่มส่งไป dominator->connector->dominator ไปเรื่อยๆ
 
 
 
ในแต่ละชั้นนั้ independent set <math>U</math> of UDG <math>G</math> จะถูกแบ่งเป็น 12 2-IS of <math>G</math> ซึ่งจะมองเป็น proper node coloring  of <math>G^2</math> ซึ่งแต่ละ subset ใน partition จะสอดคล้องกับสี หนึ่งสี
 
 
 
ทีนี้ส่วนที่น่าสนใจจะเป็นในแต่ละชั้นจะส่งข้อมูลกันอย่างไร โดยที่ไม่ชนกัน ซึ่งปัญหานี้แปลงไปเป็นปัญหา coloring ได้
 
 
 
==อื่นๆ==
 
*[[การใช้งาน gnuplot]]
 
*[[การใช้งาน Google Chart API]]
 

รุ่นแก้ไขเมื่อ 12:19, 15 กุมภาพันธ์ 2555

You have shed a ray of snushine into the forum. Thanks!