>
you're reading...
Announcements

SACT Seminar: Fast Algorithms for Diameter-Optimally Augmenting Trees

Time: 12:00 noon Tuesday, 16th August 2016.

Location: SIT 459

Speaker: Joachim Gudmundsson, University of Sydney

Title: Fast Algorithms for Diameter-Optimally Augmenting Trees

Abstract:
We consider the problem of augmenting an n-vertex graph embedded in a metric space, by inserting one additional edge in order to minimize the diameter of the resulting graph. We present exact algorithms for the cases when (i) the input graph is a path, running in O(n log^3 n) time, and (ii) the input graph is a tree, running in O(n^2  log n) time. We also present an algorithm that computes a (1+\eps)-approximation in O(n + 1/eps^3) time, for paths in R^d, where d is a constant.

Advertisements

Discussion

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 61 other followers

%d bloggers like this: