题目：A certain decomposition of graphs and searching long paths locally

报告人：陈小锋（合肥工业大学）

时间：1月11日上午10:00-11:00

地点：五教5205

摘要: In this talk, I will mainly report a method of searching long paths through any vertex in a graph using only local information, i.e., a local version of the famous Hamilton problem. The method is based on a new decomposition of graphs, where each decomposition induces a ranking of the vertices. We will first show that the ranks can be computed via searching some fixed points of certain dynamical systems on the studied graphs and this computation can be implemented locally and distributively. Then, we will derive some lower bounds and searching algorithms for the longest paths through a vertex.