Department Seminar Series
Isometric path complexity of graphs
12th December 2023, 13:00
Ashton Lecture Theatre
Dr. Dibyayan Chakraborty
School of Computing, University of Leeds
Isometric path of a graph is a shortest path between its end-vertices. A collection of isometric paths is `''rooted'' if all of them starts from the same vertex. Isometric path complexity (ipco (G)) of a graph G is the minimum number of ''rooted'' isometric paths required to cover any isometric path of the graph.
Even though this parameter was initially conceptualised to design constant factor approximation algorithms for a particular optimisation problem called "ISOMETRIC PATH COVER", it was shown to be bounded for some interesting and seemingly different graph classes.
In this talk, we will discuss the known results and some techniques to bound this parameter on interesting graph classes.