Graph Invariants Galore with Denise Gosnell

We talk with Dr. Denise Gosnell, graph consultant at DataStax about creative applications of graph technology, TOTAL DOMINATION, and some surprising use cases.

Highlights!

0:15 - David welcomes Denise back to the show

0:40 - Denise recaps how to know if you have a graph problem

1:06 - Introducing some interesting graph invariant techniques that we can apply to a variety of problems

1:55 - Chromatic numbers refer to the minimum number of colors required to color a graph so that adjacent vertices have different colors. This can be applied to scheduling problems where vertices are tasks to be scheduled, and edges represent conflicts, for example, medical operations that require same doctor, or surgery room. same room. We can use these conflict graphs to determine tasks that can occur simultaneously.

5:59 - Augmenting paths - this is single source shortest path problem. Beginning with a bi-partite graph (a graph with 2 sets of vertices that have no edges between the sets) and some preference data, we can use Dijkstra’s algorithm to identify shortest paths between the sets. An example of this is creating an academic class schedule that assigns students and classes, optimized for their preferences.

8:58 - Denise and David have a fun aside on finding your passion

9:54 - Total domination - a favorite area of research for Denise and her advisor, Dr. Teresa Haynes. Pick the smallest set of vertices such that every vertex in the graph is in the set or touches something in the set - for example, the dominating set of a star graph is the center. This is useful for problems such as determining where to place alarms in a building.  

13:53 - You didn’t realize this, but you’ve been training to solve graph problems your whole life

14:39 - Sneak previewing future graph episodes with Denise about dealing with supernodes: modeling around them, and traversing through them