you're reading...

SACT Talk: A Polynomial-Time Algorithm for Outerplanar Diameter Improvement

Time: 3:00pm Tuesday 20th May.

Location: SIT 459

Speaker: Dr. Mathias Weller

Title: A Polynomial-Time Algorithm for Outerplanar Diameter Improvement



The Outerplanar Diameter Improvement problem asks, given a graph G and
an integer D, whether it is possible to add edges to G in a way that the
resulting graph is outerplanar and has diameter at most D. We provide a
dynamic programming algorithm that solves this problem in polynomial
time. Outerplanar Diameter Improvement demonstrates several structural
analogues to the celebrated and challenging Planar Diameter Improvement
problem, where the resulting graph should, instead, be planar. The
complexity status of this latter problem is open.



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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s

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

Join 68 other followers

%d bloggers like this: