ETD system

Electronic theses and dissertations repository

 

Tesi etd-09222015-231536


Thesis type
Tesi di laurea magistrale
Author
CAIRO, MASSIMO
URN
etd-09222015-231536
Title
New Bounds for Approximating Extremal Distances in Undirected Graphs
Struttura
INFORMATICA
Corso di studi
INFORMATICA
Commissione
relatore Grossi, Roberto
Parole chiave
  • diameter
  • radius
  • eccentricity
  • approximation
  • graph
  • algorithm
Data inizio appello
09/10/2015;
Consultabilità
parziale
Data di rilascio
09/10/2018
Riassunto analitico
In this thesis, we consider the problem of computing approximations of extremal distances in undirected graphs, namely the diameter, the radius and the eccentricity of every vertex. This is a basic problem in computational graph theory: a number of recent results attracted the interest of researchers. We present some of the algorithmic techniques recently discovered to address this problem and the conditional lower bounds on its complexity, with particular focus on the relation with combinatorial and graph-theoretic aspects.<br><br>This thesis includes some results obtained by the author in collaboration with professor Roberto Grossi (thesis advisor, University of Pisa) and professor Romeo Rizzi (University of Verona), including new algorithms, conditional impossibility results, and combinatorial insights that improve our understanding of the problem. Our original contributions resulted in a paper which will be presented at the conference ACM--SIAM Symposium on Discrete Algorithms (SODA) in January 2016.
File