Algorithms for long paths in graphs

作者：Zhang Zhao^*; Li Hao

来源：Theoretical Computer Science, 2007, 377(1-3): 25-34.

DOI：10.1016/j.tcs.2007.02.012

• Hamiltonian
• long path
• neighborhood condition

We obtain a polynomial algorithm in O (nm) time to find a long path in any graph with n vertices and m edges. The length of the path is bounded by a parameter defined on neighborhood condition of any three independent vertices of the path. An example is given to show that this bound is better than several classic results.

• 出版日期2007-5-31
• 单位新疆大学