| Presentation | 1999/5/24 Computational Issues of the Jones Polynomial of a Link Keiko Imai, Hiroshi Imai, Kyoko Sekine, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | The Jones polynomial is an invariant in knot theory. It is known that the Jones polynomial of an alternating link is related to the Tutte polynomial in graph theory. The authors presented a mildly exponential algorithm to compute the Jones polynomial of a link. Although a problem of computing the Jones polynomial is #P-hard, by using the planarity it can be calculated for some large links. This note discusses several computational issues related to the algorithm. First, the case of alternating links is discussed, and a linear-time algorithm to compute the internal/external activities of a tree is given. With this, the Jones polynomial can be represented as a sum over all trees. Next, the edge ordering in the algorithm is investigated, and an open problem is given. Then, the computation of the Jones polynomial of a p-parallel (or satellite) link of a given link is discussed. With this operation, the classification power of the Jones polynomial can be enhanced with a mild increase by a factor of 4^P of the time complexity. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | COMP99-15 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1999/5/24(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Computational Issues of the Jones Polynomial of a Link |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Keiko Imai |
| 1st Author's Affiliation | Department of Information and System Engineering, Chuo University() |
| 2nd Author's Name | Hiroshi Imai |
| 2nd Author's Affiliation | Department of Information Science, University of Tokyo |
| 3rd Author's Name | Kyoko Sekine |
| 3rd Author's Affiliation | Department of Information Science, University of Tokyo |
| Date | 1999/5/24 |
| Paper # | COMP99-15 |
| Volume (vol) | vol.99 |
| Number (no) | 86 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |