PhD Seminar • Algorithms and Complexity • Reconfiguration of Graph MinorsExport this event to calendar

Monday, June 27, 2022 — 2:00 PM to 3:00 PM EDT

Please note: This PhD seminar will be given in person in DC 1304 and online.

Vijay Subramanya, PhD candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Naomi Nishimura

Under the reconfiguration framework, we consider the various ways that a target graph H is a minor of a host graph G, where a subgraph of G can be transformed into H by means of edge contraction (replacement of both endpoints of an edge by a new vertex adjacent to any vertex adjacent to either endpoint). Equivalently, an H-model of G is a labeling of the vertices of G with the vertices of H, where the contraction of all edges between identically-labeled vertices results in a graph containing representations of all edges in H.

We explore the properties of G and H that result in a connected reconfiguration graph, in which nodes represent H-models and two nodes are adjacent if their corresponding H-models differ by the label of a single vertex of G. Various operations on G or H are shown to preserve connectivity. In addition, we demonstrate properties of graphs G that result in connectivity for the target graphs K_2, K_3, and K_4, including a full characterization of graphs G that result in connectivity for K_2-models, as well as the relationship between connectivity of G and other H-models.


To join this PhD seminar on Zoom, please go to https://uwaterloo.zoom.us/j/93549077377.

Location 
DC - William G. Davis Computer Research Centre
DC 1304 | Online PhD seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
  1. 2023 (2)
    1. January (2)
  2. 2022 (245)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (12)
    5. August (29)
    6. July (23)
    7. June (17)
    8. May (20)
    9. April (24)
    10. March (22)
    11. February (16)
    12. January (19)
  3. 2021 (210)
    1. December (21)
    2. November (13)
    3. October (12)
    4. September (21)
    5. August (20)
    6. July (17)
    7. June (11)
    8. May (16)
    9. April (27)
    10. March (20)
    11. February (13)
    12. January (19)
  4. 2020 (217)
  5. 2019 (255)
  6. 2018 (217)
  7. 2017 (36)
  8. 2016 (21)
  9. 2015 (36)
  10. 2014 (33)
  11. 2013 (23)
  12. 2012 (4)
  13. 2011 (1)
  14. 2010 (1)
  15. 2009 (1)
  16. 2008 (1)