报告人：杜文学副教授，安徽大学

报告时间：2018年10月15日14:30

          2018年10月17日14:30

报告地点：数计学院4号楼229室

报告题目：On Graph Isomorphism Problem

报告摘要： Let $G$ and $H$ be two simple graphs. A bijection $\\phi:V(G)\ightarrow V(H)$ is called an {\\it isomorphism} between $G$ and $H$ if $(\\phi\\hspace{0.5mm} v_i)(\\phi\\hspace{0.5mm} v_j)\\in E(H)$ $\\Leftrightarrow$ $v_i v_j\\in E(G)$ for any two vertices $v_i$ and $v_j$ of $G$. As well-known, the problem of determining whether or not two given graphs are isomorphic is called {\\it Graph Isomorphism Problem}. In this talk we shall present some new approaches developed for GI and a deterministic algorithm solving Graph Isomorphism Problem in time $n^{ O( \\log n ) }$.

杜文学,男,1978年5月生,南开大学理学博士,现为安徽大学数学科学学院副教授.杜文学博士近期在图的自同构群的研究上取得了一系列重要进展,尤其是给出图的同构问题的拟多项式时间算法,为该问题近30年来的重大突破.

欢迎老师和研究生参加！