Search

Showing total 15 results
Start Over Search Limiters Full Text Topic polynomials
15 results

1. Distance Distribution in Reed-Solomon Codes.

Author

Li, Jiyou and Wan, Daqing

Subjects
*REED-Solomon codes, *FINITE fields, *LINEAR codes, *POLYNOMIALS, *INTEGERS, *DISTANCES
Abstract

Let $\mathbb {F}_{q}$ be the finite field of $q$ elements. In this paper we obtain bounds on the following counting problem: given a polynomial $f(x)\in \mathbb {F}_{q} [x]$ of degree $k+m$ and a non-negative integer $r$ , count the number of polynomials $g(x)\in \mathbb {F}_{q} [x]$ of degree at most $k-1$ such that $f(x)+g(x)$ has exactly $r$ roots in $\mathbb {F}_{q}$. Previously, explicit formulas were known only for the cases $m=0, 1, 2$. As an application, we obtain an asymptotic formula on the list size of the standard Reed-Solomon code $[q, k, q-k+1]_{q}$. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

2. Hermite polynomial smoothing in beam-to-beam frictional contact.

Author

Litewka, Przemysław

Subjects
*PUBLISHED errata, *PAPER, *POLYNOMIALS, *FINITE element method, *HERMITE polynomials, *MATRICES (Mathematics), *FRICTION
Abstract

In this paper a smoothing procedure is suggested for the 3D beam-to-beam contact. A smooth segment is defined basing on current position vectors of three nodes limiting two adjacent finite elements. The approximated fragment of a beam axis as a 3D curve spans between the centre points of these elements. The curve is described parametrically using three Hermite polynomials. The four boundary conditions necessary to determine the coefficients for each of these polynomials involve co-ordinates and slopes at the curve ends. The slopes are defined in terms of the element nodal co-ordinates, too. There is no dependence on nodal rotations so this formulation can be embedded in a beam analysis using any type of beam finite element. This geometric representation of the curve is incorporated into the 3D beam-to-beam frictional contact model with the penalty method used to enforce contact constraints. The residual vector and the corresponding tangent stiffness matrix are determined for the normal part of contact and for the stick or slip state of friction. A few numerical examples are presented to show the performance of the suggested smoothing procedure in the cases featuring large frictional sliding. [ABSTRACT FROM AUTHOR]

Published
2007
Full Text
View/download PDF

3. A new algorithm for the maximum weighted stable set problem in claw-free graphs

Author

Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer, Dipartimento di Ingegneria dell'Impresa [Roma], Università degli Studi di Roma Tor Vergata [Roma], Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)

Subjects
Combinatorial optimization, Computer science, 0211 other engineering and technologies, 02 engineering and technology, Polynomials, 01 natural sciences, Domain decomposition methods, Scheduling algorithms, Matching problems, Chordal graph, Polynomial-time algorithms, Longest path, ComputingMilieux_MISCELLANEOUS, decomposition theorems, 021103 operations research, Quasi-line graphs, Mathematical programming, Integer programming, Longest path problem, Graph, Modular decomposition, 010201 computation theory & mathematics, (algorithmic) complexity, Auxiliary graphs, Claw-free graphs, Mathematical transformations, Set theory, Settore MAT/09 - Ricerca Operativa, Algorithm, Algorithms, Optimization, Paper, Aerospace applications, Boolean functions, Combinatorial mathematics, Curve fitting, Dynamic programming, Evolutionary algorithms, Farm buildings, Graph theory, Linear programming, Nonlinear programming, Polynomial approximation, Reduction, Trees (mathematics), General (CO), graph reductions, international conferences, New algorithm, Polynomial-time, Reduction tools, Running in, time bound, 0102 computer and information sciences, Combinatorics, Indifference graph, Pathwidth, Cograph, [INFO]Computer Science [cs], Graph coloring, Time complexity, Discrete mathematics, 1-planar graph, Vertex (geometry), Independent set
Abstract

In this paper, we introduce two powerful graph reductions for the maximum weighted stable set (mwss) in general graphs. We show that these reductions allow to reduce the mwss in claw-free graphs to the mwss in a class of quasi-line graphs, that we call bipolar-free. For this latter class, we provide a new algorithmic decomposition theorem running in polynomial time. We then exploit this decomposition result and our reduction tools again to transform the problem to either a single matching problem or a longest path computation in an acyclic auxiliary graph (in this latter part we use some results of Pulleyblank and Shepherd [10]). Putting all the pieces together, the main contribution of this paper is a new polynomial time algorithm for the mwss in claw-free graphs. A rough analysis of the complexity of this algorithm gives a time bound of O(n6), where n is the number of vertices in the graph, and which we hope can be improved by a finer analysis. Incidentally, we prove that the mwss problem can be solved efficiently for any class of graphs that admits a "suitable" decomposition into pieces where the mwss is easy.

Published
2008