Search

Given a finite set of weighted points in $${\mathbb {R}}^d$$ R d (where there can be negative weights), the maximum box problem asks for an axis-aligned rectangle (i.e., box) such that the sum of the weights of the points that it contains is maximized. We consider that each point of the input has a probability of being present in the final random point set, and these events are mutually independent; then, the total weight of a maximum box is a random variable. We aim to compute both the probability that this variable is at least a given parameter, and its expectation. We show that even in $$d=1$$ d = 1 these computations are #P-hard, and give pseudo-polynomial time algorithms in the case where the weights are integers in a bounded interval. For $$d=2$$ d = 2 , we consider that each point is colored red or blue, where red points have weight $$+1$$ + 1 and blue points weight $$-\infty $$ - ∞ . The random variable is the maximum number of red points that can be covered with a box not containing any blue point. We prove that the above two computations are also #P-hard, and give a polynomial-time algorithm for computing the probability that there is a box containing exactly two red points, no blue point, and a given point of the plane.

We study the existence of rainbow perfect matching and rainbow Hamiltonian cycles in edge–colored graphs where every color appears a bounded number of times. We derive asymptotically tight bounds on the minimum degree of the host graph for the existence of such rainbow spanning structures. The proof uses a probabilisitic argument combined with switching techniques.

This is a post-peer-review, pre-copyedit version of an article published in Archives of computational methods in engineering. The final authenticated version is available online at: http://dx.doi.org/10.1007/s11831-019-09378-0 In its original conception, proper generalized decomposition (PGD) provides explicit parametric solutions, denoted as computational vademecums or digital abacuses, to parametric boundary value problems. The PGD approach is extended here to devise a set of algebraic tools enabling to operate with multidimensional tensor data. These tools are designed to store, compress and perform basic operations (in particular divisions) with tensors in separable format. These tools are directly producing the computational vademecums for the resulting high-dimensional tensor data. Thus, the general methodology enables performing nontrivial operations (storage, compression, division, solving linear systems of equations...) for multidimensional tensor data. The idea is based on the principle of the PGD separation, that produces a separable least squares approximation of any multidimensional function. The PGD compression is a particular case, extensively used in practice to compact the separable solution without loss of accuracy. Here, this concept is applied to algebraic tensor structures that are also seen as functions in multidimensional Cartesian domains. Moreover, a straightforward extension of this concept is devised to operate with multidimensional objects stored in the separable format. That allows creating a toolbox of PGD arithmetic operators that is publicly released at https://git.lacan.upc.edu/zlotnik/algebraicPGDtools. Numerical tests demonstrate the performance and efficiency of the toolbox, both for tensor data handling and operation and also in applications pertaining to the discretized version of boundary value problems.

The computational cost of parametric studies currently represents the major limitation to the application of simulation-based engineering techniques in a daily industrial environment. This work presents the first nonintrusive implementation of the proper generalised decomposition (PGD) in OpenFOAM, for the approximation of parametrised laminar incompressible Navier-Stokes equations. The key feature of this approach is the seamless integration of a reduced order model (ROM) in the framework of an industrially validated computational fluid dynamics software. This is of special importance in an industrial environment because in the online phase of the PGD ROM the description of the flow for a specific set of parameters is obtained simply via interpolation of the generalised solution, without the need of any extra solution step. On the one hand, the spatial problems arising from the PGD separation of the unknowns are treated using the classical solution strategies of OpenFOAM, namely the semi-implicit method for pressure linked equations (SIMPLE) algorithm. On the other hand, the parametric iteration is solved via a collocation approach. The resulting ROM is applied to several benchmark tests of laminar incompressible Navier-Stokes flows, in two and three dimensions, with different parameters affecting the flow features. Eventually, the capability of the proposed strategy to treat industrial problems is verified by applying the methodology to a parametrised flow control in a realistic geometry of interest for the automotive industry., Comment: 35 pages, 17 figures

We study the class L of link types that admit a K4-minor-free diagram, i.e., they can be projected on the plane so that the resulting graph does not contain any subdivision of K4. We prove that L is the closure of a subclass of torus links under the operation of connected sum. Using this structural result, we enumerate L and subclasses of it, with respect to the minimal number of crossings or edges in a projection of L ∈ L . Further, we enumerate (both exactly and asymptotically) all connected K4-minor-free link diagrams, all minimal connected K4-minor-free link diagrams, and all K4-minor-free diagrams of the unknot.

Gallian's survey shows that there is a big variety of labelings of graphs. By means of (di)graphs products we can establish strong relations among some of them. Moreover, due to the freedom of one of the factors, we can also obtain enumerative results that provide lower bounds on the number of nonisomorphic labelings of a particular type. In this paper, we will focus in three of the (di)graphs products that have been used in these duties: the ⊗h-product of digraphs, the weak tensor product of graphs and the weak ⊗h-product of graphs. Reseach supported by the Spanish Government under project MTM2014-60127-P and symbolically by the Catalan Research Council under grant 2014SGR1147.

Identifying and quantifying dissimilarities among graphs is a fundamental and challenging problem of practical importance in many fields of science. Current methods of network comparison are limited to extract only partial information or are computationally very demanding. Here we propose an efficient and precise measure for network comparison, which is based on quantifying differences among distance probability distributions extracted from the networks. Extensive experiments on synthetic and real-world networks show that this measure returns non-zero values only when the graphs are non-isomorphic. Most importantly, the measure proposed here can identify and quantify structural topological differences that have a practical impact on the information flow through the network, such as the presence or absence of critical links that connect or disconnect connected components., Identifying and quantifying dissimilarities among graphs is a problem of practical importance, but current approaches are either limited or computationally demanding. Here, the authors propose an efficiently computable measure for network comparison that can identify structural topological differences.

In this paper we find an exact analytical expression for the number of spanning trees in Apollonian networks. This parameter can be related to significant topological and dynamic properties of the networks, including percolation, epidemic spreading, synchronization, and random walks. As Apollonian networks constitute an interesting family of maximal planar graphs which are simultaneously small-world, scale-free, Euclidean and space filling and highly clustered, the study of their spanning trees is of particular relevance. Our results allow also the calculation of the spanning tree entropy of Apollonian networks, which then we compare with those of other graphs with the same average degree., Manuscript accepted for publication (Discrete Applied Mathematics)

Our aim is to characterize those matrices that are the response matrix of a semi-positive definite Schr?dinger operator on a circular planar network. Our findings generalize the known results and allow us to consider both nonsingular and non diagonally dominant matrices as response matrices. To this end, we define the Dirichlet-to-Robin map associated with a Schr?dinger operator on general networks, and we prove that it satisfies the alternating property which is essential to characterize the response matrices.

In an earlier paper we developed the algebraic theory of matrix polynomials. Here we introduce two algorithms for computing "dominant" solvents. Global convergence of the algorithms under certain conditions is established.

All known globally convergent iterations for the solution of a nonlinear operator equation ƒ( x ) = 0 are either nonstationary or use nonlinear information. It is asked whether there exists a globally convergent stationary iteration which uses linear information. It is proved that even if global convergence is defined in a weak sense, there exists no such iteration for as simple a class of problems as the set of all analytic complex functions having only simple zeros. It is conjectured that even for the class of all real polynomials which have real simple zeros there does not exist a globally convergent stationary iteration using linear information.

A matrix S is a solvent of the matrix polynomial $M(X) = A_0 X^m + \cdots + A_m $ if $M(S) = 0$ where $A_i ,X,S$ are square matrices. In this paper we develop the algebraic theory of matrix polynomials and solvents. We define division and interpolation, investigate the properties of block Vandermonde matrices, and define and study the existence of a complete set of solvents. We study the relation between the matrix polynomial problem and the lambda-matrix problem, which is to find a scalar $\lambda $ such that $A_0 \lambda ^m + A_1 \lambda ^{m - 1} + \cdots + A_m $ is singular.In a future paper we extend Traub’s algorithm for calculating zeros of scalar polynomials to matrix polynomials and establish global convergence properties of this algorithm for a class of matrix polynomials.