Search

In this paper, we focus on extensions of methods for interpolating rational functions from their evaluations, in the context of erroneous evaluations. This problem can be seen both from a computer algebra and a coding theory point of view. In computer algebra, this is a generalization of Simultaneous Rational Function Reconstruction with errors and multiprecision evaluations. From an error correcting codes point of view, this problem is related to the decoding of some algebraic codes such as Reed-Solomon, Derivatives or Multiplicity codes. We give conditions on the inputs of the problem which guarantee the uniqueness of the interpolant. Since we deal with rational functions, some evaluation points may be poles: a first contribution of this work is to correct any error in a scenario with poles and multiplicities that extends (Kaltofen et al., 2020). Our second contribution is to adapt rational function reconstruction for random errors , and provide better conditions for uniqueness using interleaving techniques as in (Guerrini et al., 2021). [ABSTRACT FROM AUTHOR]

Abstract: An identifying code of a graph is a dominating set such that every vertex of is distinguished from other vertices by the set of vertices in that are at distance at most 1 from . The problem of finding an identifying code of minimum possible size turned out to be a challenging problem. It was proved by N. Bertrand, I. Charon, O. Hudry and A. Lobstein that if a graph on vertices with at least one edge admits an identifying code, then a minimal identifying code has size at most . They introduced classes of graphs whose smallest identifying code is of size . Few conjectures were formulated to classify the class of all graphs whose minimum identifying code is of size . In this paper, disproving these conjectures, we classify all finite graphs for which all but one of the vertices are needed to form an identifying code. We classify all infinite graphs needing the whole set of vertices in any identifying code. New upper bounds in terms of the number of vertices and the maximum degree of a graph are also provided. [Copyright &y& Elsevier]