报告题目：On Graph Isomorphism Problem
报告人：杜文学,副教授,安徽大学
报告时间：2017年10月15日14:30, 2017年10月17日14:30
报告地点：数计学院4号楼229室
Abstract：Let $G$ and $H$ be two simple graphs. A bijection $\phi:V(G)\rightarrow 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 ) }$.
