M.S. Thesis Defense today

School of Computing Graduate Defenses
School of Computing Graduate Defenses

M.S. Thesis Defense: Oleksiy Al-saadi
Wednesday, October 20, 2021
2:30 PM (CST)
Zoom
https://unl.zoom.us/j/96302463004
Meeting ID: 963 0246 3004

“Linear Complexity of Diameter on Asteroidal Triple-Free Graphs”

In the past, it has been shown that the diameter of some asteroidal triple-free (AT-free) graphs can be found in subquadratic time. We define a property for the existence of polar pairs in graphs with dominating pairs with low diameter. Having done this, we prove lower and upper bounds for diameter and devise a linear time algorithm to find the diameter of all AT-free graphs by exploiting relative eccentricities between dominating pair nodes.

Committee:
Jitender Deogun
Lisong Xu
Vinod Variyam