ต้นไม้ทอดข้ามแบบกำหนดฮ๊อบ

Minimum bounded hop spanning tree

Name: นนทพัทธ์ วงศ์วัฒนากิจ

keyword: ต้นไม้แบบทอดข้าม (ทฤษฎีกราฟ)

LCSH: Approximation algorithms

Classification :.LCCS: QA76.9.A43

ThaSH: มหาวิทยาลัยเกษตรศาสตร์ -- วิทยานิพนธ์. วศ.ม. (วิศวกรรมคอมพิวเตอร์) 2563.

ThaSH: มหาวิทยาลัยเกษตรศาสตร์. -- สาขาวิศวกรรมคอมพิวเตอร์ -- วิทยานิพนธ์

Abstract: ในงานนี้ประกอบไปด้วยปัญหา k-hop MST บนปริภูมิแบบยุคลิด และปัญหาที่เกี่ยวข้องกับ dominating set ใน disk graph ซึ่งเป็นกรณีทั่วไปของ unit disk graph ที่ใช้กันอย่างแพร่หลายในการวิเคราะห์เซ็นเซอร์ที่เป็นเนื้อเดียวกันหรือเครือข่ายไร้สาย เมื่อพิจารณาถึงเครือข่ายที่ไม่เป็นเนื้อเดียวกัน มันจะมีประโยชน์เมื่อพิจารณา disk graph ที่มีรัศมีต่างกัน ซึ่งเรานำเสนอขั้นตอนวิธีที่เป็น PTAS สำหรับสองปัญหานี้ In this work, we considers k-hop MST problem on Euclidean space and dominating set problems in a disk praphs which is a generalzation of unit disk graphs extensively used to analyze homogeneous sensor or wireless networls. When considering heterogeneous networks, it is useful to consider disk praphs that contain disks with different radii. We present a PTAS algorithm for these problems.

มหาวิทยาลัยเกษตรศาสตร์. สำนักหอสมุด

Address: กรุงเทพมหานคร

Email: tdckulib@ku.ac.th

Name: จิตร์ทัศน์ ฝักเจริญผล

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์หลัก

Name: ธนาวินท์ รักธรรมานนท์

Role: อาจารย์ที่ปรึกษาวิทยานิพนธ์ร่วม

Created: 2563

Modified: 2568-07-14

Issued: 2568-07-14

วิทยานิพนธ์/Thesis

วิทยานิพนธ์/Thesis

application/pdf

URL: https://www.lib.ku.ac.th/KUthesis/2563/nonthaphat-won-all.pdf

CallNumber: QA76.9.A43 .น15

tha

DegreeName: วิศวกรรมศาสตรมหาบัณฑิต

Level: ปริญญาโท

Descipline: วิศวกรรมคอมพิวเตอร์

Grantor: มหาวิทยาลัยเกษตรศาสตร์

©copyrights มหาวิทยาลัยเกษตรศาสตร์

ลำดับที่.	ชื่อแฟ้มข้อมูล	ขนาดแฟ้มข้อมูล	จำนวนเข้าถึง	วัน-เวลาเข้าถึงล่าสุด
1	nonthaphat-won-all.pdf	5.27 MB

ใช้เวลา

0.027632 วินาที