기초과학VOD

BASIC SCI VOD

  •   >  
  • 연구동향
  •   >  
  • 기초과학VOD
Super Title 2018 Discrete Math 세미나
Title The reconfiguration problem for graph homomorpisms
Speaker Mark Siggers  (  Kyungpook National University  ) Date 2018-04-03
Host KIAS Place KAIST
VOD    
For problems with a discrete set of solutions, a reconfiguration problem defines solutions to be adjacent if they meet some condition of closeness, and then asks for two given solutions it there is a path between them in the set of all solutions. The reconfiguration problem for graph homomorphisms has seen fair activity in recent years. Fixing a template, the problem Recol(H) for a graph H asks if one can get from one H-colouring of a graph G to another by changing one vertex at a time, always remaining an H-colouring. If the changed vertex has a loop, it must move to an adjecent vertex Depending on H, the problem seems to be either polynomial time solvable or PSPACE-complete. We discuss many recent results in the area and work towards conjecturing for which H the problem is PSPACE-complete. This is joint work with Rick Brewster, Jae-baek Lee, Ben Moore and Jon Noel.

이 페이지에서 제공하는 정보에 만족하십니까?