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

We state in previous paper [A. Daurat, Y. Gérard, 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 giv...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2005-01, Vol.347 (1), p.432-436
Main Authors: Daurat, A., Gérard, Y., Nivat, M.
Format: Article
Language:English
Subjects:
Algorithmic complexity
Applied sciences
Computational Geometry
Computer Science
Computer science
control theory
systems
Exact sciences and technology
Miscellaneous
Partial digest problem
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We state in previous paper [A. Daurat, Y. Gérard, 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2005.05.021