Invited Talk by Prof. Kishore Kothapalli on Ear Decomposition of Graphs with Application to Path-based Problems
Efficient design and implementation of graph algorithms on modern manycore accelerators has to however contend with a host of challenges including not being able to reach full memory system throughput and irregularity. Of late, focusing on real-world graphs, researchers are addressing these challenges by using decomposition and preprocessing techniques guided by the structural properties of such graphs.
In this direction, we present a new GPU algorithm for obtaining an ear decomposition of a graph. We then study an application of the ear decomposition of a graph in solving three path-based problems on graphs such as the all-pairs-shortest-paths, and minimum cost cycle basis, and the betweenness-centrality values of nodes. Our solutions require application-specific optimization to achieve scalability.
Kishore Kothapalli is presently an Associate Professor at the International Institute of Information Technology, Hyderabad where he is working since 2006. Prior to that, he obtained his doctoral degree in Computer Science from the Johns Hopkins University, and his Masters degree in Computer Science from the Indian Institute of Technology, Kanpur. His current research interests are in parallel and distributed algorithms with focus on graphs and matrices.