Relevant bibliographies by topics / Exact polynomial

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Exact polynomial'

Author: Grafiati
Published: 26 October 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Exact polynomial.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Exact polynomial"

1

Guilloux, Antonin, and Julien Marché. "Volume function and Mahler measure of exact polynomials." Compositio Mathematica 157, no. 4 (April 2021): 809–34. http://dx.doi.org/10.1112/s0010437x21007016.

Full text
Abstract:
We study a class of two-variable polynomials called exact polynomials which contains $A$ -polynomials of knot complements. The Mahler measure of these polynomials can be computed in terms of a volume function defined on the vanishing set of the polynomial. We prove that the local extrema of the volume function are on the two-dimensional torus and give a closed formula for the Mahler measure in terms of these extremal values. This formula shows that the Mahler measure of an irreducible and exact polynomial divided by $\pi$ is greater than the amplitude of the volume function. We also prove a K-theoretic criterion for a polynomial to be a factor of an $A$ -polynomial and give a topological interpretation of its Mahler measure.
APA, Harvard, Vancouver, ISO, and other styles
2

Achter, Jeffrey, and Cassandra Williams. "Local Heuristics and an Exact Formula for Abelian Surfaces Over Finite Fields." Canadian Mathematical Bulletin 58, no. 4 (December 1, 2015): 673–91. http://dx.doi.org/10.4153/cmb-2015-050-8.

Full text
Abstract:
AbstractConsider a quartic q-Weil polynomial ƒ. Motivated by equidistribution considerations, we define, for each prime ℓ, a local factor that measures the relative frequency with which ƒ mod ℓ occurs as the characteristic polynomial of a symplectic similitude over 𝔽ℓ. For a certain class of polynomials, we show that the resulting infinite product calculates the number of principally polarized abelian surfaces over 𝔽q with Weil polynomial ƒ.
APA, Harvard, Vancouver, ISO, and other styles
3

Borwein, Peter B. "Exact Inequalities for the Norms of Factors of Polynomials." Canadian Journal of Mathematics 46, no. 4 (August 1, 1994): 687–98. http://dx.doi.org/10.4153/cjm-1994-038-8.

Full text
Abstract:
AbstractThis paper addresses a number of questions concerning the size of factors of polynomials. Let p be a monic algebraic polynomial of degree n and suppose q1q2 … qi is a monic factor of p of degree m. Then we can, in many cases, exactly determine Here ‖ . ‖ is the supremum norm either on [—1, 1] or on {|z| ≤ 1}. We do this by showing that, in the interval case, for each m and n, the n-th Chebyshev polynomial is extremal. This extends work of Gel'fond, Mahler, Granville, Boyd and others. A number of variants of this problem are also considered.
APA, Harvard, Vancouver, ISO, and other styles
4

RÜHL, WERNER, and ALEXANDER TURBINER. "EXACT SOLVABILITY OF THE CALOGERO AND SUTHERLAND MODELS." Modern Physics Letters A 10, no. 29 (September 21, 1995): 2213–21. http://dx.doi.org/10.1142/s0217732395002374.

Full text
Abstract:
Translationally invariant symmetric polynomials as coordinates for N-body problems with identical particles are proposed. It is shown that in those coordinates the Calogero and Sutherland N-body Hamiltonians, after appropriate gauge transformations, can be presented as a quadratic polynomial in the generators of the algebra sl N in finitedimensional degenerate representation. The exact solvability of these models follows from the existence of the infinite flag of such representation spaces, preserved by the above Hamiltonians. A connection with Jack polynomials is discussed.
APA, Harvard, Vancouver, ISO, and other styles
5

Chen, Yi-Chou. "Infinitely Many Eigenfunctions for Polynomial Problems: Exact Results." Journal of Applied Mathematics 2015 (2015): 1–6. http://dx.doi.org/10.1155/2015/516159.

Full text
Abstract:
LetFx, y=asxys+as-1xys-1+⋯+a0xbe a real-valued polynomial function in which the degreesofyinFx, yis greater than or equal to 1. For any polynomialyx, we assume thatT:Rx→Rxis a nonlinear operator withTyx=Fx, yx. In this paper, we will find an eigenfunctionyx∈Rxto satisfy the following equation:Fx, yx=ayxfor some eigenvaluea∈Rand we call the problemFx, yx=ayxa fixed point like problem. If the number of all eigenfunctions inFx, yx=ayxis infinitely many, we prove that (i) any coefficients ofFx, y, asx, as-1x,…, a0x, are all constants inRand (ii)yxis an eigenfunction inFx, yx=ayxif and only ifyx∈R.
APA, Harvard, Vancouver, ISO, and other styles
6

Paschos, Vangelis Th. "When polynomial approximation meets exact computation." Annals of Operations Research 271, no. 1 (July 30, 2018): 87–103. http://dx.doi.org/10.1007/s10479-018-2986-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Bhattacharyya, Rajsekhar, Robert de Mello Koch, and Michael Stephanou. "Exact multi-restricted Schur polynomial correlators." Journal of High Energy Physics 2008, no. 06 (June 27, 2008): 101. http://dx.doi.org/10.1088/1126-6708/2008/06/101.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Paschos, Vangelis Th. "When polynomial approximation meets exact computation." 4OR 13, no. 3 (July 8, 2015): 227–45. http://dx.doi.org/10.1007/s10288-015-0294-7.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Zerz, Eva, Viktor Levandovskyy, and Kristina Schindelar. "Exact linear modeling with polynomial coefficients." Multidimensional Systems and Signal Processing 22, no. 1-3 (July 1, 2010): 55–65. http://dx.doi.org/10.1007/s11045-010-0125-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Mueller, Matthias. "Polynomial Exact-3-SAT-Solving Algorithm." International Journal of Engineering & Technology 9, no. 3 (August 4, 2020): 670. http://dx.doi.org/10.14419/ijet.v9i3.30749.

Full text
Abstract:
This article describes an algorithm which is supposed by the author to be capable of solving any instance of a 3-SAT CNF in maximal O(n^15), whereby n is the variable index range within the 3-SAT CNF to solve. The presented algorithm imitates the proceeding of an exponential, fail-safe solver. This exponential solver stores internal data in m-SAT clauses, with 3 <= m <= n. The polynomial solver works similarly, but uses 3-SAT clauses only to save the same data. The paper explains how, and proves why this can be achieved. On the supposition the algorithm is correct, the P-NP-Problem would be solved with the result that the complexity classes NP and P are equal.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Exact polynomial"

1

Ouchi, Koji. "Exact polynomial system solving for robust geometric computation." Texas A&M University, 2006. http://hdl.handle.net/1969.1/4805.

Full text
Abstract:
I describe an exact method for computing roots of a system of multivariate polynomials with rational coefficients, called the rational univariate reduction. This method enables performance of exact algebraic computation of coordinates of the roots of polynomials. In computational geometry, curves, surfaces and points are described as polynomials and their intersections. Thus, exact computation of the roots of polynomials allows the development and implementation of robust geometric algorithms. I describe applications in robust geometric modeling. In particular, I show a new method, called numerical perturbation scheme, that can be used successfully to detect and handle degenerate configurations appearing in boundary evaluation problems. I develop a derandomized version of the algorithm for computing the rational univariate reduction for a square system of multivariate polynomials and a new algorithm for a non-square system. I show how to perform exact computation over algebraic points obtained by the rational univariate reduction. I give a formal description of numerical perturbation scheme and its implementation.
APA, Harvard, Vancouver, ISO, and other styles
2

Norhazwani, Md Yunos. "Polynomial-Space Exact Algorithms for Traveling Salesman Problem in Degree Bounded Graphs." 京都大学 (Kyoto University), 2017. http://hdl.handle.net/2433/225741.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Van-'T-Hof, Pim. "Exploiting structure to cope with NP-hard graph problems : polynomial and exponential time exact algorithms." Thesis, Durham University, 2010. http://etheses.dur.ac.uk/285/.

Full text
Abstract:
An ideal algorithm for solving a particular problem always finds an optimal solution, finds such a solution for every possible instance, and finds it in polynomial time. When dealing with NP-hard problems, algorithms can only be expected to possess at most two out of these three desirable properties. All algorithms presented in this thesis are exact algorithms, which means that they always find an optimal solution. Demanding the solution to be optimal means that other concessions have to be made when designing an exact algorithm for an NP-hard problem: we either have to impose restrictions on the instances of the problem in order to achieve a polynomial time complexity, or we have to abandon the requirement that the worst-case running time has to be polynomial. In some cases, when the problem under consideration remains NP-hard on restricted input, we are even forced to do both. Most of the problems studied in this thesis deal with partitioning the vertex set of a given graph. In the other problems the task is to find certain types of paths and cycles in graphs. The problems all have in common that they are NP-hard on general graphs. We present several polynomial time algorithms for solving restrictions of these problems to specific graph classes, in particular graphs without long induced paths, chordal graphs and claw-free graphs. For problems that remain NP-hard even on restricted input we present exact exponential time algorithms. In the design of each of our algorithms, structural graph properties have been heavily exploited. Apart from using existing structural results, we prove new structural properties of certain types of graphs in order to obtain our algorithmic results.
APA, Harvard, Vancouver, ISO, and other styles
4

Lazare, Arnaud. "Global optimization of polynomial programs with mixed-integer variables." Thesis, Université Paris-Saclay (ComUE), 2019. http://www.theses.fr/2019SACLY011.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à l'étude des programmes polynomiaux, c'est à dire les problème d'optimisation dont la fonction objectif et/ou les contraintes font intervenir des polynômes de plusieurs variables. Ces problèmes ont de nombreuses applications pratiques et constituent actuellement un champ de recherche très actif. Différentes méthodes permettent de les résoudre de façon exacte ou approchée, en utilisant par exemple des relaxationssemidéfinies positives du type "moments-somme de carrés". Mais ces problèmes restent très difficiles et on ne sait résoudre en toute généralité que des instances de petite taille.Dans le cas quadratique, une approche de résolution exacte efficace a été initialement proposée à travers la méthode QCR. Elle se base sur une reformulation quadratique convexe "optimale" au sens de la borne par relaxation continue.Une des motivations de cette thèse est de généraliser cette approche pour le cas des problèmes polynomiaux. Dans la majeure partie de ce manuscrit, nous étudions les problèmes d'optimisation en variables binaires. Nous proposons deux familles de reformulations convexes pour ces problèmes: des reformulations "directes" et des reformulations passant par la quadratisation.Pour les reformulations directes, nous nous intéressons tout d'abord aux linéarisations. Nous introduisons le concept de q-linéarisation, une linéarisation utilisant q variables additionnelles, et comparons les bornes obtenues par relaxation continue pour différentes valeurs de q. Ensuite, nous appliquons la reformulation convexe au problème polynomial, en ajoutant des termes supplémentaires à la fonction objectif, mais sans ajouter de variables ou de contraintes additionnelles.La deuxième famille de reformulations convexes vise à étendre la reformulation quadratique convexe au cas polynomial. Nous proposons plusieurs nouvelles reformulations alternatives que nous comparons aux méthodes existantes sur des instances de la littérature. En particulier nous présentons l'algorithme PQCR pour résoudre des problèmes polynomiaux binaires sans contrainte. La méthode PQCR permet de résoudre des instances jusqu'ici non résolues. En plus des expérimentations numériques, nous proposons aussi une étude théorique visant à comparer les différentes reformulations quadratiques de la littérature puis à leur appliquer une reformulation convexe.Enfin nous considérons des cas plus généraux et nous proposons une méthode permettant de calculer des relaxations convexes pour des problèmes continus
In this thesis, we are interested in the study of polynomial programs, that is optimization problems for which the objective function and/or the constraints are expressed by multivariate polynomials. These problems have many practical applications and are currently actively studied. Different methods can be used to find either a global or a heuristic solution, using for instance, positive semi-definite relaxations as in the "Moment/Sum of squares" method. But these problems remain very difficult and only small instances are addressed. In the quadratic case, an effective exact solution approach was initially proposed in the QCR method. It is based on a quadratic convex reformulation, which is optimal in terms of continuous relaxation bound.One of the motivations of this thesis is to generalize this approach to the case of polynomial programs. In most of this manuscript, we study optimization problems with binary variables. We propose two families of convex reformulations for these problems: "direct" reformulations and quadratic ones.For direct reformulations, we first focus on linearizations. We introduce the concept of q-linearization, that is a linearization using q additional variables, and we compare the bounds obtained by continuous relaxation for different values of q. Then, we apply convex reformulation to the polynomial problem, by adding additional terms to the objective function, but without adding additional variables or constraints.The second family of convex reformulations aims at extending quadratic convex reformulation to the polynomial case. We propose several new alternative reformulations that we compare to existing methods on instances of the literature. In particular we present the algorithm PQCR to solve unconstrained binary polynomial problems. The PQCR method is able to solve several unsolved instances. In addition to numerical experiments, we also propose a theoretical study to compare the different quadratic reformulations of the literature and then apply a convex reformulation to them.Finally, we consider more general problems and we propose a method to compute convex relaxations for continuous problems
APA, Harvard, Vancouver, ISO, and other styles
5

Naldi, Simone. "Exact algorithms for determinantal varieties and semidefinite programming." Thesis, Toulouse, INSA, 2015. http://www.theses.fr/2015ISAT0021/document.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à l'étude des structures déterminantielles apparaissent dans l'optimisation semi-définie (SDP), le prolongement naturel de la programmation linéaire au cône des matrices symétrique semi-définie positives. Si l'approximation d'une solution d'un programme semi-défini peut être calculé efficacement à l'aide des algorithmes de points intérieurs, ni des algorithmes exacts efficaces pour la SDP sont disponibles, ni une compréhension complète de sa complexité théorique a été atteinte. Afin de contribuer à cette question centrale en optimisation convexe, nous concevons un algorithme exact pour décider la faisabilité d'une inégalité matricielle linéaire (LMI) $A(x)\succeq 0$. Quand le spectraèdre associé (le lieu $\spec$ des $x \in \RR^n$ ou $A(x)\succeq 0$) n'est pas vide, la sortie de cet algorithme est une représentation algébrique d'un ensemble fini qui contient au moins un point $x \in \spec$: dans ce cas, le point $x$ minimise le rang de $A(x)$ sur $\spec$. La complexité est essentiellement quadratique en le degré de la représentation en sortie, qui coïncide, expérimentalement, avec le degré algébrique de l'optimisation semi-définie. C'est un garantie d'optimalité de cette approche dans le contexte des algorithmes exacts pour les LMI et la SDP. Remarquablement, l'algorithme ne suppose pas la présence d'un point intérieur dans $\spec$, et il profite de l'existence de solutions de rang faible de l'LMI $A(x)\succeq 0$. Afin d'atteindre cet objectif principal, nous développons une approche systématique pour les variétés déterminantielles associées aux matrices linéaires. Nous prouvons que décider la faisabilité d'une LMI $A(x)\succeq 0$ se réduit à calculer des points témoins dans les variétés déterminantielles définies sur $A(x)$. Nous résolvons ce problème en concevant un algorithme exact pour calculer au moins un point dans chaque composante connexe réelle du lieu des chutes de rang de $A(x)$. Cet algorithme prend aussi avantage des structures supplémentaires, et sa complexité améliore l'état de l'art en géométrie algébrique réelle. Enfin, les algorithmes développés dans cette thèse sont implantés dans une nouvelle bibliothèque Maple appelé Spectra, et les résultats des expériences mettant en évidence la meilleure complexité sont fournis
In this thesis we focus on the study of determinantal structures arising in semidefinite programming (SDP), the natural extension of linear programming to the cone of symetric positive semidefinite matrices. While the approximation of a solution of a semidefinite program can be computed efficiently by interior-point algorithms, neither efficient exact algorithms for SDP are available, nor a complete understanding of its theoretical complexity has been achieved. In order to contribute to this central question in convex optimization, we design an exact algorithm for deciding the feasibility of a linear matrix inequality (LMI) $A(x) \succeq 0$. When the spectrahedron $\spec = \{x \in \RR^n \mymid A(x) \succeq 0\}$ is not empty, the output of this algorithm is an algebraic representation of a finite set meeting $\spec$ in at least one point $x^*$: in this case, the point $x^*$ minimizes the rank of the pencil on the spectrahedron. The complexity is essentially quadratic in the degree of the output representation, which meets, experimentally, the algebraic degree of semidefinite programs associated to $A(x)$. This is a guarantee of optimality of this approach in the context of exact algorithms for LMI and SDP. Remarkably, the algorithm does not assume the presence of an interior point in the spectrahedron, and it takes advantage of the existence of low rank solutions of the LMI. In order to reach this main goal, we develop a systematic approach to determinantal varieties associated to linear matrices. Indeed, we prove that deciding the feasibility of a LMI can be performed by computing a sample set of real solutions of determinantal polynomial systems. We solve this problem by designing an exact algorithm for computing at least one point in each real connected component of the locus of rank defects of a pencil $A(x)$. This algorithm admits as input generic linear matrices but takes also advantage of additional structures, and its complexity improves the state of the art in computational real algebraic geometry. Finally, the algorithms developed in this thesis are implemented in a new Maple library called {Spectra}, and results of experiments highlighting the complexity gain are provided
APA, Harvard, Vancouver, ISO, and other styles
6

Mehrabdollahei, Mahya. "La mesure de Mahler d’une famille de polynômes exacts." Thesis, Sorbonne université, 2022. https://accesdistant.sorbonne-universite.fr/login?url=https://theses-intra.sorbonne-universite.fr/2022SORUS170.pdf.

Full text
Abstract:
Dans cette thèse, nous étudions la suite de mesures de Mahler d’une famille de polynômes à deux variables exacts et réguliers, que nous notons Pd := P0≤i+j≤d xiyj . Elle n’est bornée ni en volume, ni en genre de la courbe algébrique sous-jacente. Nous obtenons une expression pour la mesure de Mahler de Pd comme somme finie de valeurs spéciales du dilogarithme de Bloch-Wigner. Nous utilisons SageMath pour approximer m(Pd) pour 1 ≤ d ≤ 1000. En recourant à trois méthodes différentes, nous prouvons que la limite de la suite de mesures de Mahler de cette famille converge vers 92π2 ζ(3). De plus, nous calculons le développement asymptotique de la mesure de Mahler de Pd et prouvons que sa vitesse de convergence est de O(log dd2 ). Nous démontrons également une généralisation du théorème de Boyd-Lawton, affirmant que les mesures de Mahler multivariées peuvent être approximéess en utilisant les mesures de Mahler de dimension inférieure. Enfin, nous prouvons que la mesure de Mahler de Pd pour d arbitraire peut être écrite comme une combinaison linéaire de fonctions L associées à un caractère de Dirichlet primitif impair. Nous calculons finalement explicitement la représentation de la mesure de Mahler de Pd en termes de fonctions L, pour 1 ≤ d ≤ 6
In this thesis we investigate the sequence of Mahler measures of a family of bivariate regular exact polynomials, called Pd := P0≤i+j≤d xiyj , unbounded in both degree and the genus of the algebraic curve. We obtain a closed formula for the Mahler measure of Pd in termsof special values of the Bloch–Wigner dilogarithm. We approximate m(Pd), for 1 ≤ d ≤ 1000,with arbitrary precision using SageMath. Using 3 different methods we prove that the limitof the sequence of the Mahler measure of this family converges to 92π2 ζ(3). Moreover, we compute the asymptotic expansion of the Mahler measure of Pd which implies that the rate of the convergence is O(log dd2 ). We also prove a generalization of the theorem of the Boyd-Lawton which asserts that the multivariate Mahler measures can be approximated using the lower dimensional Mahler measures. Finally, we prove that the Mahler measure of Pd, for arbitrary d can be written as a linear combination of L-functions associated with an odd primitive Dirichlet character. In addition, we compute explicitly the representation of the Mahler measure of Pd in terms of L-functions, for 1 ≤ d ≤ 6
APA, Harvard, Vancouver, ISO, and other styles
7

Toufayli, Laila. "Stabilisation polynomiale et contrôlabilité exacte des équations des ondes par des contrôles indirects et dynamiques." Phd thesis, Université de Strasbourg, 2013. http://tel.archives-ouvertes.fr/tel-00780215.

Full text
Abstract:
La thèse est portée essentiellement sur la stabilisation et la contrôlabilité de deux équations des ondes moyennant un seul contrôle agissant sur le bord du domaine. Dans le cas du contrôle dynamique, le contrôle est introduit dans le système par une équation différentielle agissant sur le bord. C'est en effet un système hybride. Le contrôle peut être aussi applique directement sur le bord d'une équation, c'est le cas du contrôle indirecte mais non borne. La nature du système ainsi coupledépend du couplage des équations, et ceci donne divers résultats par la stabilisation (exponentielle et polynomiale) et la contrôlabilité exacte (espace contrôlable). Des nouvelles inégalités d'énergie permettent de mettre en oeuvre la Méthode fréquentielle et la Méthode d'Unicité de Hilbert.
APA, Harvard, Vancouver, ISO, and other styles
8

Potts, Daniel, and Toni Volkmer. "Fast, exact and stable reconstruction of multivariate algebraic polynomials in Chebyshev form." Universitätsbibliothek Chemnitz, 2015. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-160992.

Full text
Abstract:
We describe a fast method for the evaluation of an arbitrary high-dimensional multivariate algebraic polynomial in Chebyshev form at the nodes of an arbitrary rank-1 Chebyshev lattice. Our main focus is on conditions on rank-1 Chebyshev lattices allowing for the exact reconstruction of such polynomials from samples along such lattices and we present an algorithm for constructing suitable rank-1 Chebyshev lattices based on a component-by-component approach. Moreover, we give a method for the fast, exact and stable reconstruction.
APA, Harvard, Vancouver, ISO, and other styles
9

Valvo, Daniel William. "Repairing Cartesian Codes with Linear Exact Repair Schemes." Thesis, Virginia Tech, 2020. http://hdl.handle.net/10919/98818.

Full text
Abstract:
In this paper, we develop a scheme to recover a single erasure when using a Cartesian code,in the context of a distributed storage system. Particularly, we develop a scheme withconsiderations to minimize the associated bandwidth and maximize the associateddimension. The problem of recovering a missing node's data exactly in a distributedstorage system is known as theexact repair problem. Previous research has studied theexact repair problem for Reed-Solomon codes. We focus on Cartesian codes, and show wecan enact the recovery using a linear exact repair scheme framework, similar to the oneoutlined by Guruswami and Wooters in 2017.
Master of Science
Distributed storage systems are systems which store a single data file over multiple storage nodes. Each storage node has a certain storage efficiency, the "space" required to store the information on that node. The value of these systems, is their ability to safely store data for extended periods of time. We want to design distributed storage systems such that if one storage node fails, we can recover it from the data in the remaining nodes. Recovering a node from the data stored in the other nodes requires the nodes to communicate data with each other. Ideally, these systems are designed to minimize the bandwidth, the inter-nodal communication required to recover a lost node, as well as maximize the storage efficiency of each node. A great mathematical framework to build these distributed storage systems on is erasure codes. In this paper, we will specifically develop distributed storage systems that use Cartesian codes. We will show that in the right setting, these systems can have a very similar bandwidth to systems build from Reed-Solomon codes, without much loss in storage efficiency.
APA, Harvard, Vancouver, ISO, and other styles
10

Mazoit, Frédéric. "Décomposition algorithmique des graphes." Phd thesis, Ecole normale supérieure de lyon - ENS LYON, 2004. http://tel.archives-ouvertes.fr/tel-00148807.

Full text
Abstract:
Dans cette thèse, nous nous intéressons à deux types de décompositions des graphes introduits par Robertson et Seymour: les décompositions arborescentes et les décompositions en branches. À ces décompositions sont associés deux paramètres des graphes: la largeur arborescente et la largeur de branches. Nous montrons que ces deux décompositions peuvent être vues comme issues d'une même structure combinatoire; les deux paramètres mentionné ci-dessus sont égaux aux valeurs minimales de deux paramètres de cette structure commune. En poussant plus avant cette analogie, nous montrons comment adapter une technique de calcul de la largeur arborescente au calcul de la largeur de branches. Ceci nous permet de calculer la largeur de branches des graphes de nombre astéroïde borné ayant un nombre polynômial de séparateurs minimaux et celle des graphes d-trapézoïdes circulaires. Ce parallèle nous permet aussi d'adapter certains résultats structurels sur les décompositions en branches aux décompositions arborescentes. Dans le cas des graphes planaires, nous interprétons ces propriétés à l'aide d'outils topologiques. De cette façon, nous donnons une démonstration simple d'un théorème de dualité reliant la largeur arborescente d'un graphe planaire et celle de son dual. Ces outils nous permettent aussi d'énumérer de façon efficace les séparateurs minimaux des graphes planaires.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Exact polynomial"

1

Alzofon, Frederick E. Two methods for the exact solution of diffraction problems. Bellingham, WA: SPIE Optical Engineering Press, 2004.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Two methods for the exact solution of diffraction problems. Bellingham, WA: SPIE Press, 2003.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Yan, Liu. Exact integrations of polynomials and symmetric quadrature formulas over arbitrary polyhedral grids. Moffett Field, Calif: National Aeronautics and Space Administration, Ames Research Center, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
4

Exact integrations of polynomials and symmetric quadrature formulas over arbitrary polyhedral grids. Moffett Field, Calif: Ames Research Center, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "Exact polynomial"

1

Kratsch, Stefan, and Magnus Wahlström. "Two Edge Modification Problems without Polynomial Kernels." In Parameterized and Exact Computation, 264–75. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-11269-0_22.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Hermelin, Danny, Stefan Kratsch, Karolina Sołtys, Magnus Wahlström, and Xi Wu. "A Completeness Theory for Polynomial (Turing) Kernelization." In Parameterized and Exact Computation, 202–15. Cham: Springer International Publishing, 2013. http://dx.doi.org/10.1007/978-3-319-03898-8_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Galbiati, G., and F. Maffioli. "Exact Matroid Parity and Polynomial Identities." In Operations Research ’93, 180–89. Heidelberg: Physica-Verlag HD, 1994. http://dx.doi.org/10.1007/978-3-642-46955-8_47.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chakraborty, Chiranjit, and Rahul Santhanam. "Instance Compression for the Polynomial Hierarchy and beyond." In Parameterized and Exact Computation, 120–34. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33293-7_13.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Adiga, Abhijin, Jasine Babu, and L. Sunil Chandran. "Polynomial Time and Parameterized Approximation Algorithms for Boxicity." In Parameterized and Exact Computation, 135–46. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-33293-7_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Fellows, Michael R. "The Lost Continent of Polynomial Time: Preprocessing and Kernelization." In Parameterized and Exact Computation, 276–77. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006. http://dx.doi.org/10.1007/11847250_25.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Aravind, N. R., R. B. Sandeep, and Naveen Sivadasan. "On Polynomial Kernelization of $$\mathcal {H}$$ -free Edge Deletion." In Parameterized and Exact Computation, 28–38. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-13524-3_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Jansen, Bart M. P., and Stefan Kratsch. "On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal." In Parameterized and Exact Computation, 132–44. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-28050-4_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Gutin, Gregory, Stefan Kratsch, and Magnus Wahlström. "Polynomial Kernels and User Reductions for the Workflow Satisfiability Problem." In Parameterized and Exact Computation, 208–20. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-13524-3_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Kotek, Tomer, and Johann A. Makowsky. "The exact complexity of the Tutte polynomial." In Handbook of the Tutte Polynomial and Related Topics, 175–93. Boca Raton: Chapman and Hall/CRC, 2022. http://dx.doi.org/10.1201/9780429161612-9.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Exact polynomial"

1

Qin, Xiaolin, Yong Feng, Jingwei Chen, and Jingzhong Zhang. "Finding exact minimal polynomial by approximations." In the 2009 conference. New York, New York, USA: ACM Press, 2009. http://dx.doi.org/10.1145/1577190.1577211.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Castella, Marc. "Exact Inversion of MIMO Nonlinear Polynomial Mixtures." In 2007 IEEE International Conference on Acoustics, Speech, and Signal Processing. IEEE, 2007. http://dx.doi.org/10.1109/icassp.2007.367115.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Li, Qiang, Wing-Kin Ma, and Qiong Wu. "Hyperspectral Super-Resolution: Exact Recovery In Polynomial Time." In 2018 IEEE Statistical Signal Processing Workshop (SSP). IEEE, 2018. http://dx.doi.org/10.1109/ssp.2018.8450697.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Chen, Jing-wei, Yong Feng, Xiao-lin Qin, and Jing-zhong Zhang. "Exact polynomial factorization by approximate high degree algebraic numbers." In the 2009 conference. New York, New York, USA: ACM Press, 2009. http://dx.doi.org/10.1145/1577190.1577199.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Demirtas, Sefa, Guolong Su, and Alan V. Oppenheim. "Exact and approximate polynomial decomposition methods for signal processing applications." In ICASSP 2013 - 2013 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2013. http://dx.doi.org/10.1109/icassp.2013.6638689.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Bonifaci, Vincenzo, Alberto Marchetti-Spaccamela, Nicole Megow, and Andreas Wiese. "Polynomial-Time Exact Schedulability Tests for Harmonic Real-Time Tasks." In 2013 IEEE 34th Real-Time Systems Symposium (RTSS). IEEE, 2013. http://dx.doi.org/10.1109/rtss.2013.31.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Jiang, Albert Xin, and Kevin Leyton-Brown. "Polynomial-time computation of exact correlated equilibrium in compact games." In the 12th ACM conference. New York, New York, USA: ACM Press, 2011. http://dx.doi.org/10.1145/1993574.1993593.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Yunos, N. M., A. Shurbevski, and H. Nagamochi. "Polynomial-space exact algorithm for TSP in degree-5 graphs." In 12th International Symposium on Operations Research and its Applications in Engineering, Technology and Management (ISORA 2015). Institution of Engineering and Technology, 2015. http://dx.doi.org/10.1049/cp.2015.0608.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Townsend, M. A., and S. Gupta. "Automated Modeling and Rapid Solution of Robot Dynamics Using the Symbolic Polynomial Technique." In ASME 1987 Design Technology Conferences. American Society of Mechanical Engineers, 1987. http://dx.doi.org/10.1115/detc1987-0068.

Full text
Abstract:
Abstract Fast and accurate solutions of the dynamic equations of a robot arm are required for real time on-line control. In this paper we present a new method for rapidly evaluating the exact dynamic state of a robot. This method uses a combination of symbolic and numerical computations on the equations of motion, which are developed in the form of polynomials — hence the name, the symbolic polynomial technique.
APA, Harvard, Vancouver, ISO, and other styles
10

Lin, Chuen-Sen, and Bao-Ping Jia. "Use of Resultant in the Dimensional Synthesis of Linkage Components: Motion Generation With Prescribed Timing." In ASME 1992 Design Technical Conferences. American Society of Mechanical Engineers, 1992. http://dx.doi.org/10.1115/detc1992-0333.

Full text
Abstract:
Abstract Resultant theory is applied to derive closed-form solutions for the dimensional synthesis of linkage components for a finite number of precision positions for motion generation with prescribed timing. The solutions are in forms of polynomial equations of the exponential of a single unknown angular displacement. The degree of the derived polynomial depends on the number of links in the linkage component and the number of precision positions to be synthesized for, or the number of compatibility equations. The resultant theory is discussed in detail, and the procedure for the derivation of resultant polynomials is demonstrated. This paper shows that, for the case of two compatibility equations, the solution is a six-degree polynomial. For the case of three compatibility equations, the solution is a fifty-fourth degree polynomial. The Bernshtein formula is applied to check the exact number of solutions of the original system of polynomial equations and to verify the validity of the derived resultant polynomials. An algorithm is also proposed for screening out extra solutions which may be generated through the solution process.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Exact polynomial"

1

Zarrieß, Benjamin, and Anni-Yasmin Turhan. Most Specific Generalizations w.r.t. General EL-TBoxes. Technische Universität Dresden, 2013. http://dx.doi.org/10.25368/2022.196.

Full text
Abstract:
In the area of Description Logics the least common subsumer (lcs) and the most specific concept (msc) are inferences that generalize a set of concepts or an individual, respectively, into a single concept. If computed w.r.t. a general EL-TBox neither the lcs nor the msc need to exist. So far in this setting no exact conditions for the existence of lcs- or msc-concepts are known. This report provides necessary and suffcient conditions for the existence of these two kinds of concepts. For the lcs of a fixed number of concepts and the msc we show decidability of the existence in PTime and polynomial bounds on the maximal roledepth of the lcs- and msc-concepts. The latter allows to compute the lcs and the msc, respectively.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Exact polynomial' for particular source types:
Journal articles Dissertations / Theses
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography