Graph reconstruction and verification via distance oracles – University of Copenhagen

Graph reconstruction and verification via distance oracles

DIKU’s Centre for Efficient Algorithms and Data Structures (EADS) invite you to sit in on a talk by Zhou Hang.

Zhou Hang is a PhD student at École Normale Supérieure de Paris, specializing in graph algorithms for combinatorial optimization.

Abstract

We study the problem of reconstructing a hidden graph G given access to a distance oracle, when G can only be accessed by querying pairs of vertices and getting their shortest path distance in G. We wish to design randomized algorithms with small query complexity. We also study approximate reconstruction.

Further, we explore the verification problem, in which we are given a mental picture of some unknown graph and wish to verify that our mental image is correct with few queries. We make progress on those problems for graphs of bounded degree, outerplanar graphs, and graphs of bounded tree width.

(Joint work with Claire Mathieu and Sampath Kannan)

Hosted by the EADS Center/Mikkel Thorup