Spring 2015: Theory Seminar
ICS, Room 243, 1:00pm
May 1, 2015:

Fixed-Parameter Tractable Algorithms for Crossing Minimization in Book Embeddings

Will Devanny

Having a good model for a social network is vital in their analysis. We study a family of social network models known as dK distributions from a computational perspective. Previous work has found the 1K and 2K distributions to be tractable, but for 3K distributions the literature has resorted to using heuristics. We show computational problems related to the 3K distributions are NP-hard by a reduction from coloring. We also show similar alternative models suffer from the same problem.

Joint work with David Eppstein, Athina Markopoulou, and Balint Tillman.