Some necessary clarifications about the chords' problem and the Partial Digest Problem

被引：12

作者：

Daurat, A

Gérard, Y

Nivat, M

机构：

[1] LSIIT, F-67400 Illkirch Graffenstaden, France

[2] Ensemble Univ Cezeaux, IUT, LLAIC, F-63172 Aubiere, France

[3] LIAFA, F-75251 Paris, France

来源：

THEORETICAL COMPUTER SCIENCE | 2005年 / 347卷 / 1-2期

关键词：

Partial Digest Problem; algorithmic complexity;

D O I：

10.1016/j.tcs.2005.05.021

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We state in previous paper [A. Daurat, Y. Gerard, M. Nivat, The chords' problem, Theoret. Comput. Sci. 282(2) (2002) 319-336] that the chords' problem can be solved in polynomial time. This result is however ambiguous and some people have been abused because the encoding of the data has not been given. The correctness of the result requires to specify the encoding of the data that we have used and to highlight the difference with the usual encoding implicitly considered in Partial Digest Problem. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：432 / 436

页数：5

共 10 条

[1] Bianchi G, 2002, J DIFFER GEOM, V60, P177
[2] Cieliebak M, 2003, LECT N BIOINFORMAT, V2812, P111
[3] The chords' problem
Daurat, A
Gérard, Y
Nivat, M
[J]. THEORETICAL COMPUTER SCIENCE, 2002, 282 (02) : 319 - 336
[4] Sums, projections, and sections of lattice sets, and the discrete covariogram
Gardner, RJ
Gronchi, P
Zong, CM
[J]. DISCRETE & COMPUTATIONAL GEOMETRY, 2005, 34 (03) : 391 - 409
[5] Jones NC., 2004, An Introduction to Bioinformatics Algorithms
[6] KALTOFEN E, COMPLEXITY FACTORING
[7] Lemke P, 2003, ALGORITHM COMBINAT, V25, P597
[8] Lemke P., 1988, COMPLEXITY INVERTING
[9] FACTORING POLYNOMIALS WITH RATIONAL COEFFICIENTS
LENSTRA, AK
LENSTRA, HW
LOVASZ, L
[J]. MATHEMATISCHE ANNALEN, 1982, 261 (04) : 515 - 534
[10] SKIENA SS, 1990, PROCEEDINGS OF THE SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY, P332, DOI 10.1145/98524.98598

← 1 →