Skip to content

Dr. Naomi Nishimura

When:
Tuesday, 23rd October 2018 1:00 pm
Where: E2-320

Title: Reconfiguring Subgraphs and Graph Minors

In this talk, I will present two recent results in the area of combinatorial reconfiguration, in the process providing both a primer for those unfamiliar with the reconfiguration framework and insights into new directions for those already familiar with previous work in the area.  Reconfiguration provides a way of exploring the relationships among configurations (typically solutions to an instance of a problem), where a reconfiguration step transforms one configuration into another by a small, incremental change.
 
In the result on subgraphs, each configuration is a subset of edges or vertices of an input graph that form a subgraph in a specified class.  We consider the complexity of determining whether or not one configuration can be transformed (or, is reconfigurable) to another by a sequence of reconfiguration steps for different choices of graph classes and representations of subgraphs.
 
In studying graph minors, we consider each configuration to be a labeling of the vertices of a graph G by the vertices of a graph H.  We then determine the properties of both G and H that result in each configuration being reconfigurable to any other.
 
No previous knowledge of reconfiguration or graph minors is assumed.
Complete Seminar List
© 2011 University of Manitoba Department of Computer Science
Back to top