PIMS - UManitoba Computer Science Lecture: Naomi Nishimura

  • Date: 10/23/2018
  • Time: 13:00
Naomi Nishimura, UWaterloo

University of Manitoba


Reconfiguring Subgraphs and Graph Minors


n 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.

Other Information: 

Time: 1:00pm

Location: E2-320