Link Theory from the Computational Topological Viewpoint

计算拓扑视角下的链路理论

基本信息

批准号：
17540135
负责人：
HARA Masao
金额：
$ 2.04万
依托单位：
Tokai University
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

项目摘要

Alexander polynomial of a link can be calculated in polynomial time from a link diagram. It is known that calculating Jones polynomial or other skein polynomials from a diagram is #P-hard. Therefore it seems impossible that Jones polynomial is calculated in polynomial time. For some classes of diagrams it is known that we can calculate the Jones polynomial of the links in polynomial time if the class contains its diagram.In this research, we design a fast algorithm that calculates Kauffman bracket polynomial of a 2-bridge link diagram and a closed 3-braid link diagram. Our algorithm takes O(n) operations of polynomials, where n is the number of crossings of the diagram. Since the degrees of the polynomials that are used are O(n) and the coefficients are O(n) size integers, it takes O(n^2 log n) time word operations. Jones polynomial of a link can be calculated from Kauffinan bracket polynomial and writhe of its diagram in linear time.Moreover, we show that Kauffinan bracket polynomial of Montesinos link diagrams can be calculated in O(n^2 log n) time. The branched double covering space of the 3-sphere branched along a 2-bridge link or a Montesinos link is a Seifert fiber space whose base space is a 2-sphere. The branched covering space of a 2-bridge link has at most 2 singular fibers and the branched covering space of a Montesinos link has 3 or more singular fibers.

链接的亚历山大多项式可以在多项式时间内从链接图中计算出来。众所周知，从图中计算琼斯多项式或其他绞线多项式是＃p-hard。因此，琼斯多项式似乎不可能在多项式时间内计算。对于某些类别的图表，众所周知，如果该类包含其图，我们可以在多项式时间内计算链接的琼斯多项式。在这项研究中，我们设计了一种快速算法，该算法可以计算Kauffman支架的2桥链接图和2-桥链接图的多项式封闭的3架链接图。我们的算法采用多项式的O（n）操作，其中n是该图的交叉数。由于所使用的多项式的程度为O（n），系数为O（n）大小整数，因此需要O（n^2 log n）时间单词操作。链接的琼斯多项式可以通过线性时间的曲线式多项式和其图的writhe计算。此外，我们表明可以在o（n^2 log n）时间中计算蒙特西诺斯链路图的高芬群括号多项式。沿着2桥连接或蒙特西诺斯链路分支的三个球杆的分支双覆盖空间是一个塞弗特纤维空间，其基本空间为2秒。 2桥连接的分支覆盖空间最多具有2个单数纤维，而蒙特西诺斯链路的支覆盖空间具有3个或更多的奇异纤维。

项目成果

期刊论文数量（0）

专著数量（0）

科研奖励数量（0）

会议论文数量（0）

专利数量（0）

Fast algorithms for computing Jones polynomials of certain links

DOI：
10.1016/j.tcs.2006.11.012
发表时间：
2007-04
期刊：
Theor. Comput. Sci.
影响因子：
0
作者：
Masahiko Murakami;Masao Hara;Makoto Yamamoto;Sei'ichi Tani
通讯作者：
Masahiko Murakami;Masao Hara;Makoto Yamamoto;Sei'ichi Tani

Polynomial Time Inductive Inference of Unions of Two Term Tree Languages

两项树语言并集的多项式时间归纳推理

DOI：
发表时间：
2006
期刊：
Proc.the 16th International Conference on Inductive Logic Programming (Short Papers)(ILP 2006)
影响因子：
0
作者：
K.;Inata;T.;Miyahara;H.;Ueda;K.;Takahashi;Hitoshi Yamasaki;Hidenori Hirashima
通讯作者：
Hidenori Hirashima

Fast Algorithms for Computing Jones Polynomial of Certain Links

计算某些链接的琼斯多项式的快速算法

DOI：
发表时间：
2005
期刊：
4^<th> Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
影响因子：
0
作者：
Masahiko Murakami;Masao Hara;Makoto Yamamoto;Seiichi Tani
通讯作者：
Seiichi Tani

A Fast Algorithm for Computing Jones Polynomials of Montesinos Links

计算Montesinos链路琼斯多项式的快速算法