All events are in Central time unless specified.

M.S. Thesis Defense: Oleksiy Al-saadi

2:30 pm–3:30 pm
M.S. Thesis Defense: Oleksiy Al-saadi

Wednesday, October 20, 2021
2:30 PM (CST)
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.

Jitender Deogun
Lisong Xu
Vinod Variyam

Download this event to my calendar