Department Seminar Series

Isometric path complexity of graphs

12th December 2023, 13:00 add to calenderAshton 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.
add to calender (including abstract)

Additional Materials