A polynomial time approximation scheme for the two-source minimum routing cost spanning trees

Let G be an undirected graph with nonnegative edge lengths. Given two vertices as sources and all vertices as destinations, we investigated the problem how to construct a spanning tree of G such that the sum of distances from sources to destinations is minimum. In the paper, we show the NP-hardness of the problem and present a polynomial time approximation scheme. For any >0, the approximation scheme finds a (1+)-approximation solution in O(n^1/+1) time. We also generalize the approximation algorithm to the weighted case for distances that form a metric space.     

Strong periodicity of links and the coefficients of the Conway polynomial

Przytycki and Sokolov proved that a three-manifold admits a semi-free action of the finite cyclic group of order with a circle as the set of fixed points if and only if is obtained from the three-sphere by surgery along a strongly -periodic link . Moreover, if the quotient three-manifold is an integral homology sphere, then we may assume that is orbitally separated. This paper studies the behavior of the coefficients of the Conway polynomial of such a link. Namely, we prove that if is a strongly -periodic orbitally separated link and is an odd prime, then the coefficient is congruent to zero modulo for all such that .

     

Bounding Poincaré‐Hopf indices and Milnor numbers

We use Mather's finite determinacy theory and Baum‐Bott's theorem to give sharp bounds for the Poincaré‐Hopf index of a germ of homolorphic vector field with an isolated zero. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A fully polynomial bicriteria approximation scheme for the constrained spanning tree problem

We propose a fully polynomial bicriteria approximation scheme for the constrained spanning tree problem. First, an exact pseudo-polynomial algorithm is developed based on a two-variable extension of the well-known matrix-tree theorem. The scaling and approximate binary search techniques are then utilized to yield a fully polynomial approximation scheme.     

Harmonic and refined Rayleigh–Ritz for the polynomial eigenvalue problem

After reviewing the harmonic Rayleigh–Ritz approach for the standard and generalized eigenvalue problem, we discuss several extraction processes for subspace methods for the polynomial eigenvalue problem. We generalize the harmonic and refined Rayleigh–Ritz approaches which lead to new approaches to extract promising approximate eigenpairs from a search space. We give theoretical as well as numerical results of the methods. In addition, we study the convergence of the Jacobi–Davidson method for polynomial eigenvalue problems with exact and inexact linear solves and discuss several algorithmic details. Copyright © 2008 John Wiley & Sons, Ltd.     

Dimers, tilings and trees

Generalizing results of Temperley (London Mathematical Society Lecture Notes Series 13 (1974) 202), Brooks et al. (Duke Math. J. 7 (1940) 312) and others (Electron. J. Combin. 7 (2000); Israel J. Math. 105 (1998) 61) we describe a natural equivalence between three planar objects: weighted bipartite planar graphs; planar Markov chains; and tilings with convex polygons. This equivalence provides a measure-preserving bijection between dimer coverings of a weighted bipartite planar graph and spanning trees of the corresponding Markov chain. The tilings correspond to harmonic functions on the Markov chain and to “discrete analytic functions” on the bipartite graph.The equivalence is extended to infinite periodic graphs, and we classify the resulting “almost periodic” tilings and harmonic functions.     

Proof of the Loebl–Komlós–Sós conjecture for large, dense graphs

The Loebl–Komlós–Sós conjecture states that for any integers k and n, if a graph G on n vertices has at least n/2 vertices of degree at least k, then G contains as subgraphs all trees on k+1 vertices. We prove this conjecture in the case when k is linear in n, and n is sufficiently large.     

A polynomial algorithm to compute the minimum degree spanning trees of directed acyclic graphs with applications to the broadcast problem

In this paper, we focus on the directed minimum degree spanning tree problem and the minimum time broadcast problem. Firstly, we propose a polynomial time algorithm for the minimum degree spanning tree problem in directed acyclic graphs. The algorithm starts with an arbitrary spanning tree, and iteratively reduces the number of vertices of maximum degree. We can prove that the algorithm must reduce a vertex of the maximum degree for each phase, and finally result in an optimal tree. The algorithm terminates in O(mnlogn) time, where m and n are the numbers of edges and vertices of the graph, respectively. Moreover, we apply the new algorithm to the minimum time broadcast problem. Two consequences for directed acyclic graphs are: (1) the problem under the vertex-disjoint paths mode can be approximated within a factor of of the optimum in O(mnlogn)-time; (2) the problem under the edge-disjoint paths mode can be approximated within a factor of O(Δ^*/logΔ^*) of the optimum in O(mnlogn)-time, where Δ^* is the minimum k such that there is a spanning tree of the graph with maximum degree k.     

Generalized harmonic numbers,Jacobi numbers and a Hankel determinant evaluation

In this paper we will introduce a sequence of complex numbers that are called the Jacobi numbers. This sequence generalizes in a natural way several sequences that are known in the literature, such as Catalan numbers, central binomial numbers, generalized catalan numbers, the coefficient of the Hilbert matrix and others. Subsequently, using a study of the polynomial of Jacobi, we give an evaluation of the Hankel determinants that associated with the sequence of Jacobi numbers. Finally, by finding a relationship between the Jacobi numbers and generalized harmonic numbers, we determine the evaluation of the Hankel determinants that are associated with generalized harmonic numbers.     

Caffarelli–Kohn–Nirenberg inequalities on Lie groups of polynomial growth

In the setting of a Lie group of polynomial volume growth, we derive inequalities of Caffarelli–Kohn–Nirenberg type, where the weights involved are powers of the Carnot–Caratheodory distance associated with a fixed system of vector fields which satisfy the Hörmander condition. The use of weak spaces is crucial in our proofs and we formulate these inequalities within the framework of Lorentz spaces (a scale of (quasi)‐Banach spaces which extend the more classical Lebesgue spaces) thereby obtaining a refinement of, for instance, Sobolev and Hardy–Sobolev inequalities.     

Relations,models and a memetic approach for three degree-dependent spanning tree problems

In this paper we take into account three different spanning tree problems with degree-dependent objective functions. The main application of these problems is in the field of optical network design. In particular, we propose the classical Minimum Leaves Spanning Tree problem as a relevant problem in this field and show its relations with the Minimum Branch Vertices and the Minimum Degree Sum Problems. We present a unified memetic algorithm for the three problems and show its effectiveness on a wide range of test instances.     

A stabilized finite element method based on local polynomial pressure projection for the stationary Navier–Stokes equations

This article considers a stabilized finite element approximation for the branch of nonsingular solutions of the stationary Navier–Stokes equations based on local polynomial pressure projection by using the lowest equal-order elements. The proposed stabilized method has a number of attractive computational properties. Firstly, it is free from stabilization parameters. Secondly, it only requires the simple and efficient calculation of Gauss integral residual terms. Thirdly, it can be implemented at the element level. The optimal error estimate is obtained by the standard finite element technique. Finally, comparison with other methods, through a series of numerical experiments, shows that this method has better stability and accuracy.     

Symmetry classes of spanning trees of Aztec diamonds and perfect matchings of odd squares with a unit hole

We say that two graphs are similar if their adjacency matrices are similar matrices. We show that the square grid G _n of order n is similar to the disjoint union of two copies of the quartered Aztec diamond QAD _n−1 of order n−1 with the path P _n ⁽²⁾ on n vertices having edge weights equal to 2. Our proof is based on an explicit change of basis in the vector space on which the adjacency matrix acts. The arguments verifying that this change of basis works are combinatorial. It follows in particular that the characteristic polynomials of the above graphs satisfy the equality P(G _n )=P(P _n ⁽²⁾)[P(QAD _n−1)]². On the one hand, this provides a combinatorial explanation for the “squarishness” of the characteristic polynomial of the square grid—i.e., that it is a perfect square, up to a factor of relatively small degree. On the other hand, as formulas for the characteristic polynomials of the path and the square grid are well known, our equality determines the characteristic polynomial of the quartered Aztec diamond. In turn, the latter allows computing the number of spanning trees of quartered Aztec diamonds. We present and analyze three more families of graphs that share the above described “linear squarishness” property of square grids: odd Aztec diamonds, mixed Aztec diamonds, and Aztec pillowcases—graphs obtained from two copies of an Aztec diamond by identifying the corresponding vertices on their convex hulls. We apply the above results to enumerate all the symmetry classes of spanning trees of the even Aztec diamonds, and all the symmetry classes not involving rotations of the spanning trees of odd and mixed Aztec diamonds. We also enumerate all but the base case of the symmetry classes of perfect matchings of odd square grids with the central vertex removed. In addition, we obtain a product formula for the number of spanning trees of Aztec pillowcases. Research supported in part by NSF grant DMS-0500616.     

Chung–Yau Invariants and Graphs with Symmetric Hitting Times

The Chung–Yau graph invariants were originated from Chung–Yau's work on discrete Green's function. We show how they could be used to derive new explicit formulas and estimates for hitting times of random walks. We also apply them to study graphs with symmetric hitting times.     

Conservation laws for Camassa–Holm equation, Dullin–Gottwald–Holm equation and generalized Dullin–Gottwald–Holm equation

In this paper we construct the conservation laws for the Camassa–Holm equation, the Dullin–Gottwald–Holm equation (DGH) and the generalized Dullin–Gottwald–Holm equation (generalized DGH). The variational derivative approach is used to derive the conservation laws. Only first order multipliers are considered. Two multipliers are obtained for the Camassa–Holm equation. For the DGH and generalized DGH equations the variational derivative approach yields two multipliers; thus two conserved vectors are obtained.     

q‐Bernstein polynomials related to q‐Frobenius–Euler polynomials,l‐functions,and q‐Stirling numbers

The aim of this paper was to derive new identities and relations associated with the q‐Bernstein polynomials, q‐Frobenius–Euler polynomials, l‐functions, and q‐Stirling numbers of the second kind. We also give some applications related to theses polynomials and numbers. Copyright © 2012 John Wiley & Sons, Ltd.     

Two examples of trilinear forms whose approximation numbers satisfy the appropriate summability properties but which are not nuclear or of Hilbert–Schmidt type

We give two examples of trilinear forms defined on Hilbert spaces such that the first one is not nuclear but the series of its approximations numbers is convergent and the second one is not a Hilbert–Schmidt form but the series of the square of its approximation numbers is convergent.     

An inverse polynomial method for the identification of the leading coefficient in the Sturm–Liouville operator from boundary measurements

An inverse polynomial method of determining the unknown leading coefficient k=k(x) of the linear Sturm–Liouville operator Au=−(k(x)u^′(x))^′+q(x)u(x), x(0,1), is presented. As an additional condition only two measured data at the boundary (x=0,x=1) are used. In absence of a singular point (u^′(x)≠0,u^″(x)≠0,x[0,1]) the inverse problem is classified as a well-conditioned . If there exists at least one singular point, then the inverse problem is classified as moderately ill-conditioned (u^′(x₀)=0,x₀(0,1);u^′(x)≠0,x≠x₀;u^″(x)≠0,x[0,1]) and severely ill-conditioned (u^′(x₀)=u^″(x₀)=0,x₀(0,1);u^′(x)≠0,u^″(x)≠0,x≠x₀). For each of the cases direct problem solution is approximated by corresponding polynomials and the inverse problem is reformulated as a Cauchy problem for to the first order differential equation with respect the unknown function k=k(x). An approximate analytical solution of the each Cauchy problems are derived in explicit form. Numerical simulations all the above cases are given for noise free and noisy data. An accuracy of the presented approach is demonstrated on numerical test solutions.     

On the colored Jones polynomial, sutured Floer homology, and knot Floer homology

Let K⊂S³, and let denote the preimage of K inside its double branched cover, Σ(S³,K). We prove, for each integer n>1, the existence of a spectral sequence whose E² term is Khovanov's categorification of the reduced n-colored Jones polynomial of (mirror of K) and whose E^∞ term is the knot Floer homology of (when n odd) and of (S³,K#Kr) (when n even). A corollary of our result is that Khovanov's categorification of the reduced n-colored Jones polynomial detects the unknot whenever n>1.