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

这项研究的目的是研究结，链接和图形的拓扑不变的拓扑剂的空气。 （2003）让L为链接，c L的图表的交叉数。 （2004年）我们为打结问题构建了一个交互式证明系统，并证明了该问题包含在IP中。因此，毫无打结的问题都包含在AM和Co-Am.3中。 （2004年）我们提供了快速的算法，用于计算2-桥链接和封闭3-编织图的jones多项式。给定具有N边缘的TAIT图，这些算法以o（n）程度o（n）多项式的o（n）算术操作运行，其中n是链接图的交叉数。4。 （2005年），我们提供了快速的算法，用于计算2-桥链接和封闭3-架链路的琼斯多项式的算法。给定带有N边缘的Tait图，这些算法以O（n^2log n）时间运行。5。 （2005年）我们给出了一种快速算法，用于从整数序列列表中计算蒙特西诺斯链接的琼斯多项式。给定代表带有n个交叉点的链路图的整数序列列表，该算法以o（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)。

Fast algorithms for computing Jones polynomials of certain links

• DOI: 10.1016/j.tcs.2006.11.012
• 发表时间: 2007-04
• 期刊: Theor. Comput. Sci.
• 作者: Masahiko Murakami;Masao Hara;Makoto Yamamoto;Sei'ichi Tani

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

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