Organizer: Blair D. Sullivan
This seminar will use a broad interpretation of "CS theory," and will include talks on related topics in areas such as graph theory.
Unless otherwise noted, talks will be in
EBII, Room 3211
Centennial Campus, NCSU
Now in its third year, we officially have a preferred day and time (Monday, 11:00 am) for the seminar, and plan to have approximately one talk per month. Please double-check the schedule, though, as out-of-town speakers may necessitate a change in day. please sign up for our mailing list (directions at the bottom of this page) to receive notification of all talks, times, and locations.
Sponsors: The 2015-2016 seminars have been made possible thanks to support from KPIT, the ePartners program, and the NC State Engineering Foundation, and the NC State Department of Computer Science
Irene Muzi, Sapienza University of Rome
Wednesday April 13, 2016: 3:00 pm EBII-3211
Please note the unusual day and time!
The 1/p-IntegralLinkage Problem in Directed Acyclic Graphs
Given a graph G and distinct ordered pairs of vertices (s_1,t_1),...,(s_k,t_k), the k-VertexDisjointPaths (k-VDP) problem asks for pairwise vertex disjoint paths P_1,...,P_k such that P_i is a path from s_i to t_i. k-VDP is a classical problem in graph theory both in its undirected and directed version. For undirected graphs, Robertson and Seymour showed that k-VDP is solvable in polynomial time when k is fixed. The directed case is considerably harder and it was shown to be NP-hard even when k equals 2 (a result of Fortune, Hopcroft and Wyllie). In this talk we will focus on the 1/p-IntegralLinkage problem, a relaxation of k-VDP that allows for a vertex of G to belong to at most p of the k paths and we will show that a fixed parameter time algorithm exists on directed acyclic graphs when p equals k-1. This is joint work with K. Edwards and P. Wollan.
Scheduled Talks for Current Academic Year
October 5, 2015, 11:00 am: Dana Randall, Georgia Institute of Technology. Phase Transitions in Random Structures and Sampling Algorithms.
November 2, 2015 11:00 am: Jeremy Kun, University of Illinois, Chicago. Resilience and new approaches to approximate graph coloring.
November 23, 2015, 11:00 am: Claire Monteleoni, George Washington University. Climate Informatics: Algorithms, Advances, and Open Problems.
January 11, 2016 11:00 am: Liz Munch, University at Albany, SUNY. The Reeb graph interleaving distance
February 22, 2016 11:00 am: Aaron Clauset, University of Colorado, Boulder. Gender, Productivity, and Prestige in Computer Science Faculty Hiring Networks
March 28, 2016 11:00 am: David Gleich, Purdue University. Sparsity and localization in evaluating functions of matrices on modern information networks.
April 13, 2016 3:00 pm: Irene Muzi, Sapienza University of Rome. TBA.
postponed to Fall 2016 : Cris Moore, Santa Fe Institute. TBA.
Previous Seminars (with abstracts)
To subscribe to the theory seminar announcement mailing list, send an email
message to the NCSU list server at firstname.lastname@example.org with "SUBSCRIBE cstheoryseminar" in the body of the message (not the subject line).