On computational algorithms of invariatns of links and graphs

关于链接和图不变性的计算算法

• 批准号: 14540136
• 负责人: YAMAMOTO Makoto
• 金额: $ 1.54万
• 依托单位: CHUO UNIVERSITY
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 2004
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-14540136/
• 关键词: knot; link; topological invariant; Jones polynomial; interactive proof system; computational topology; 計算量; アルゴリズム; グラフ理論; 量子アルゴリズム

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).

本研究的目的是研究求纽结、链环和图的拓扑不变量的算法，我们的结果如下：1。（2003）设L是一条链路，c是L的图的交叉数。我们证明了树形链路的琼斯多项式是用O（c ^3）次多项式的运算来计算的。（2004）我们构造了一个关于打结问题的交互式证明系统，并证明了该问题包含在IP中。因此，解结问题包含在AM和co-AM中。（2004）给出了从2-桥链和闭3-辫链的Tait图计算它们的Jones多项式的快速算法。给定一个有n条边的Tait图，这些算法运行的次数为O（n）的多项式的算术运算，其中n是链接的交叉点的数量。（2005）给出了从2-桥链和闭3-辫链的Tait图计算它们的Jones多项式的快速算法。对于一个有n条边的Tait图，这些算法的时间复杂度为O（n^2log n）。（2005）我们给出了一个从整数序列表计算Montesinos链的Jones多项式的快速算法。给定一个整数序列列表，表示具有n个交叉点的链接图，该算法运行O（n）次多项式的操作。

项目成果

Unknotting is an AM ∩co-AM

解开结是 AM ∩co-AM

• 发表时间: 2005
• 期刊: Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithm
• 作者: M.Hara;M.Yamamoto;S.Tani
• 通讯作者: S.Tani

An Algorithm of Computing Jones Polynomials of Closed 3-braid links in linear time

线性时间内计算闭合三辫链琼斯多项式的算法

• 发表时间: 2003
• 期刊: FIT 2003
• 作者: M.Murakami;M.Hara;M.Yamamoto;S.Tani
• 通讯作者: S.Tani

Makoto Yamamoto, M.Murakami, M.Hara, S.Tani: "Fast algorithms of computing Jones polynomials of certain liks"研究集会「結び目のトポロジーVI」記録. 83-92 (2004)

Makoto Yamamoto、M.Murakami、M.Hara、S.Tani：“计算某些喜欢的琼斯多项式的快速算法”研究会议“结的拓扑 VI”83-92 (2004)。

Arborescent絡み目に対するジョーンズ多項式計算アルゴリズム

树状连杆的琼斯多项式计算算法

• 发表时间: 2002
• 期刊: FIT2002情報科学技術フォーラム情報技術レターズ 1
• 作者: 山本 慎;原 正雄;谷 聖一
• 通讯作者: 谷 聖一

山本慎, 村上雅彦, 原正雄, 谷聖一: "閉3組み紐絡み目のジョーンズ多項式を計算する線形時間アルゴリズム"情報科学技術フォーラム2003. 121-122 (2003)

Shin Yamamoto、Masahiko Murakami、Masao Hara、Seiichi Tani：“计算闭合三辫链路琼斯多项式的线性时间算法”信息科学技术论坛 2003. 121-122 (2003)