On computational algorithms of invariatns of links and graphs

点击翻译按钮获取中文摘要

The purpose of this research is to study alogrithms of cmuting topologizal invariants of knots, links and graphs.Our results are followings:1. (2003) Let L be a link, c the number of crossings of a diagram of L. We showed that the Jones polynomial of an arborescent link is computed with O(c^3) operations of polynomials of degree O(c).2. (2004) We constructed an interactive proof system for the Knotting Problem, and proved that the problem is contained in IP. Consequently, the Unknotting Problem is contained in both AM and co-AM.3. (2004) We gave fast algorithms for computing Jones polynomials of 2--bridge links and closed 3--braid links from their Tait graphs. Given a Tait graph with n edges, these algorithms run with O(n) arithmetic operations of polynomials of degree O(n), where n is the number of the crossings of the link diagram.4. (2005) We gave fast algorithms for computing Jones polynomials of 2--bridge links and closed 3--braid links from their Tait graphs. Given a Tait graph with n edges, these algorithms run in O(n^2log n) time.5. (2005) We gave a fast algorithm for computing Jones polynomials of Montesinos links from lists of integer sequences. Given a list of integer sequences that represents a link diagram with n crossings, this algorithm runs with O(n) operations of polynomials of degree O(n).