1. Faculté des Sciences
  2. Accueil
  3. Agenda

Diameter computations ind shortest paths problems

Publié le 16 mai 2019 Mis à jour le 16 mai 2019

May 24th, 2019, 4:00 PM, room: NO906

Michel Habib (Université de Paris)

Abstract

Computing the diameter of a graph (maximum number of edges on a shortest path) is a fundamental graph problem with countless applications in computer science and beyond. Unfortunately, the textbook algorithm for computing the diameter of an n-vertex m-edge graph takes O(nm)-time. This quadratic running-time is too prohibitive for large graphs with millions of nodes.

 

The radius and diameter of a graph are part of the basic global parameters that allow to apprehend the structure of a practical graph. More broadly, the eccentricity of each node, defined as the furthest distance from the node, is also of interest as a classical centrality measure. It is tightly related to radius which is the minimum eccentricity and to diameter which is the maximum eccentricity.

On the one hand, efficient computation of such parameters is still theoretically challenging as truly sub-quadratic algorithms would improve the state of the art for other ``hard in P'' related problems such as finding two orthogonal vectors in a set of vectors or testing if one set in a collection is a hitting set for another collection. A sub-quadratic diameter algorithm would also refute the strong exponential time hypothesis (SETH) and would improve the state of the art of SAT solvers. I will explain the reduction between deciding if the diameter of a split graph is 2 or 3 and a subexponential algorithm for SAT. Then I will propose a kind of dichotomy result for split graphs trying to fix the boarder between linear and quadratic algorithms.

On the other hand, a line of practical algorithms has been proposed based on performing selected Breadth First Search traversals (BFS) allowing to compute the diameter of very large graphs. However, such practical efficiency is still not well understood. We propose a notion of certificate that helps to capture the efficiency of these practical algorithms.

I will finish with a survey of the practical algorithms that compute shortest paths in road networks and some open problems involving dynamic networks.

Bio

Michel Habib is professor emeritus in Computer Science at University Paris Diderot - Paris 7, UFR d’Informatique. He is a member of both the research group Algorithms and discrete structures and the INRIA Paris research team Gang. His research is mainly focused on classic algorithms on discrete structures with special interest for graphs and orders, including:

  • Well structured classes of graphs and orders
  • Graph decompositions with special interest to modular decomposition
  • Graph searching with special interest to LexBFS (Lexicographic Breadth First Search) and LexDFS (Lexicographic Depth First Search)
  • Applications to biology (Phylogeny and Networks analysis)
  • Practical Algorithms for huge graphs
  • Algorithms for finding regularities in huge graphs

The speaker is hosted by Jean-Paul Doignon.

http://di.ulb.ac.be/seminaires/

Date(s)
Le 24 mai 2019