Isometric path complexity of graphs

12^th December 2023, 13:00 Ashton Lecture Theatre
Dr. Dibyayan Chakraborty
School of Computing, University of Leeds

Abstract

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.

Additional Materials

• https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.32