>
you're reading...
Announcements

SACT Talk: Computational complexity, taut structures and triangulations

Time: 11am Friday, 25th May, 2012
Location: SIT 124 Boardroom
Speaker: Benjamin Burton, University of Queensland

Abstract:
There are many interesting and difficult algorithmic problems in
low-dimensional topology.  Here we study the problem of finding a taut
structure on a 3-manifold triangulation, whose existence has implications
for both the geometry and combinatorics of the triangulation.  We prove
that detecting taut structures is “hard”, in the sense that it is NP-complete.
We also prove that detecting taut structures is “not too hard”, by showing
it to be fixed-parameter tractable.  This is joint work with Jonathan Spreer.

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 64 other followers

%d bloggers like this: