W&M Featured Events
This calendar presented by
William & Mary
[PAST EVENT] Honors Thesis Defense (Sarah Kunkler)
April 23, 2012
5pm - 6pm
Abstract: We show that finding a graph realization with the minimum Randic index for a given degree sequence is solvable in polynomial time. This is shown by reducing to the minimum perfect weight b-matching problem. Using the b-matching problem, we find the realization with the minimum Randic index, but this graph is not guaranteed to be connected. In this case, we have developed a heuristic to connect the graph using two-switches, which preserves the degree sequence. From our experiments, the Randic index of the realization after our heuristic has a much lower percent difference from the minimum Randic index than that between the original and the minimum Randic index.
Contact
Rex Kincaid