MSc Thesis Proposal Announcement of Patrick Devaney:"Approximating Average Bounded-Angle Minimum Spanning Trees"

Wednesday, November 2, 2022 - 10:00 to 11:30


The School of Computer Science is pleased to present… 

MSc Thesis Proposal by: Patrick Devaney 

Date: Wednesday November 2nd, 2022 
Time:  10:00am-11:30am 
Location: Lambton Tower, Room 3105 
Reminder: Two-part attendance required: Part I (Scan the QR code, fill in online form) and Part II (sign in sheet). *Make sure you are in the room at least 5-10 minutes BEFORE the presentation starts – once the presentation has begun, latecomers will not be admitted.


Motivated by the problem of orienting directional antennas in wireless communication networks, we study average bounded-angle minimum spanning trees. Let P be a set of points in the plane and let α be an angle. An α-spanning tree (α-ST) of P is a spanning tree of the complete Euclidean graph induced by P with the restriction that all edges incident to each point p in P lie in a wedge of angle α with apex p. An α-minimum spanning tree (α-MST) of P is an α-ST with minimum total edge length.
An average-α-spanning tree (denoted by avg-α-ST) is a spanning tree with the relaxed condition that incident edges to all points lie in wedges with average angle α. An average-α-minimum spanning tree (avg-α-MST) is an α-ST with minimum total edge length. We focus on α = 2π/3. Let A(2π/3) be the smallest ratio of the length of the 2π/3-MST to the length of the standard MST, over all sets of points in the plane. Biniaz, Bose, Lubiw, and Maheshwari (Algorithmica 2022) showed that 4/3 ≤ A (2π/3) ≤ 3/2. We improve the upper bound and show that A(2π/3) ≤ 13/9. We further examine other values of α. 
Keywords: minimum spanning tree (MST), bounded angle MST, approximation algorithm, wireless communication networks, antennas, Euclidean graph

MSc Thesis Committee:  

Internal Reader: Dr. Asish Mukhopadhyay            
External Reader: Dr. Adrian Zahariuc       
Advisor: Dr. Ahmad Biniaz  
Co-Advisor: Dr. Prosenjit Bose 

MSc Thesis Proposal Announcement 

5113 Lambton Tower 401 Sunset Ave. Windsor ON, N9B 3P4 (519) 253-3000 Ext. 3716