8 documentos corresponden a la consulta.
Palabras contadas: computational: 54, complexity: 78
Figueira, S. - Nies, A. - Stephan, F.
Electron. Notes Theor. Comput. Sci. 2006;143(SPEC ISS):45-57
2006
Temas: ω-r.e. - K-triviality - Kolmogorov complexity - Lowness - Traceability - Combinatorial mathematics - Computational complexity - Number theory - ω-r.e. - K-triviality
Descripción: Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Burzyn, P. - Bonomo, F. - Durán, G.
Discrete Appl Math 2006;154(13 SPEC ISS):1824-1844
2006
Temas: Computational complexity - Edge modification problems - Graph classes - NP-completeness - Algorithms - Computational complexity - Graph theory - Set theory - Theorem proving - Edge modification problems
Descripción: Fil:Burzyn, P. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Durán, G. - Lin, M.C. - Mera, S. - Szwarcfiter, J.L.
Discrete Appl Math 2006;154(13 SPEC ISS):1783-1790
2006
Temas: Algorithms - Circular-arc graphs - Clique-independent sets - Helly circular-arc graphs - Algorithms - Computational complexity - Computational methods - Mathematical models - Set theory - Circular-arc graphs
Descripción: Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Perrucci, D. - Sabia, J.
J. Discrete Algorithms 2007;5(3):471-478
2007
Temas: Complexity - Real roots - Straight line program - Approximation theory - Computational complexity - Integer programming - Problem solving - Real roots - Straight line program - Polynomials
Descripción: We give a new proof of the NP-hardness of deciding the existence of real roots of an integer univariate polynomial encoded by a straight line program based on certain properties of the Tchebychev polynomials. These techniques allow us to prove some new NP-hardness results related to real root approximation for polynomials given by straight line programs. © 2006 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
De Leo, M. - Dratman, E. - Matera, G.
J. Complexity 2005;21(4):502-531
2005
Temas: Complexity - Conditioning - Homotopy algorithms - Polynomial system solving - Semi-linear parabolic problems - Stationary solutions - Algorithms - Boundary value problems - Mathematical models - Matrix algebra
Descripción: We consider a family of polynomial systems which arises in the analysis of the stationary solutions of a standard discretization of certain semi-linear second-order parabolic partial differential equations. We prove that this family is well-conditioned from the numeric point of view, and ill-conditioned from the symbolic point of view. We exhibit a polynomial-time numeric algorithm solving any member of this family, which significantly contrasts the exponential behavior of all known symbolic algorithms solving a generic instance of this family of systems. © 2005 Elsevier Inc. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Bank, B. - Giusti, M. - Heintz, J. - Pardo, L.M.
J. Complexity 2005;21(4):377-412
2005
Temas: Arithmetic circuit - Arithmetic network - Complexity - Elimination procedure - Geometric degree - Geometry of polar varieties and its generalizations - Real polynomial equation solving - Algorithms - Computational complexity - Digital arithmetic
Descripción: Let V be a closed algebraic subvariety of the n-dimensional projective space over the complex or real numbers and suppose that V is non-empty and equidimensional. The classic notion of a polar variety of V associated with a given linear subvariety of the ambient space of V was generalized and motivated in Bank et al. (Kybernetika 40 (2004), to appear). As particular instances of this notion of a generalized polar variety one reobtains the classic one and an alternative type of a polar variety, called dual. As main result of the present paper we show that for a generic choice of their parameters the generalized polar varieties of V are empty or equidimensional and smooth in any regular point of V. In the case that the variety V is affine and smooth and has a complete intersection ideal of definition, we are able, for a generic parameter choice, to describe locally the generalized polar varieties of V by explicit equations. Finally, we indicate how this description may be used in order to design in the context of algorithmic elimination theory a highly efficient, probabilistic elimination procedure for the following task: In case, that the variety V is ℚ-definable and affine, having a complete intersection ideal of definition, and that the real trace of V is non-empty and smooth, find for each connected component of the real trace of V an algebraic sample point. © 2005 Elsevier Inc. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
Bonomo, F. - Marenco, J. - Saban, D. - Stier-Moses, N.E.
Discrete Appl Math 2012;160(18):2573-2590
2012
Temas: Maximum edge subgraph problem - Polyhedral combinatorics - Quasi-cliques - Branch-and-cut algorithms - Computational studies - Integer programming formulations - Polyhedral approach - Polyhedral combinatorics - Polyhedral studies - Polytopes
Descripción: The study of cohesive subgroups is an important aspect of social network analysis. Cohesive subgroups are studied using different relaxations of the notion of clique in a graph. For instance, given a graph and an integer k, the maximum edge subgraph problem consists of finding a k-vertex subset such that the number of edges within the subset is maximum. This work proposes a polyhedral approach for this NP-hard problem. We study the polytope associated to an integer programming formulation of the problem, present several families of facet-inducing valid inequalities, and discuss the separation problem associated to these families. Finally, we implement a branch and cut algorithm for this problem. This computational study illustrates the effectiveness of the classes of inequalities presented in this work. © 2011 Elsevier B.V. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo
D'Alfonso, L. - Jeronimo, G. - Solernó, P.
J. Complexity 2006;22(3):396-430
2006
Temas: Differential algebra - Differential Hilbert function - Elimination theory - Probabilistic algorithms - Resolvent representation - Straight-line programs - Algorithms - Computation theory - Differential equations - Functions
Descripción: We prove upper bounds on the order and degree of the polynomials involved in a resolvent representation of the prime differential ideal associated with a polynomial differential system for a particular class of ordinary first order algebraic-differential equations arising in control theory. We also exhibit a probabilistic algorithm which computes this resolvent representation within time polynomial in the natural syntactic parameters and the degree of a certain algebraic variety related to the input system. In addition, we give a probabilistic polynomial-time algorithm for the computation of the differential Hilbert function of the ideal. © 2005 Elsevier Inc. All rights reserved.
...ver más Tipo de documento: info:ar-repo/semantics/artículo