Synthesis of Layered Perovskite Oxides, ACa2-xLaxNb3-xTix010 (A = K, Rb, Cs), and Characterization of New Solid Acids, HCa2-xLaxNb3-xTixOlo (0 < x d 2), Exhibiting Variable Bronsted Acidity?

Layered perovskite oxides of the formula ACa~,La,Nb3-,Ti,010 (A = K, Rb, Cs and 0 < x d 2) have been prepared. The members adopt the structures of the parent ACazNb3010. Interlayer alkali cations in the niobium-titanium oxide series can be ion-exchanged with Li+, Na+, NH4+, or H+ to give new derivatives. Intercalation of the protonated derivatives with organic bases reveals that the Bronsted acidity of the solid solution series, HC~ ~ , L ~ ,N~ ~ , T ~ ,dOep~eOnd, s on the titanium content. While the x = 1 member (HCaLaNbzTiOlo) is nearly as acidic as the parent HCazNb3010, the x = 2 member (HLazNbTizOlo) is a weak acid hardly intercalating organic bases with pKa - 11.3. The variation of acidity is probably due to an ordering of Nb/Ti atoms in the triple octahedral perovskite slabs, [Ca~,La,Nb~,Ti,0~0], such that protons are attached to NbO6 octahedra in the x = 1 member and to Ti06 octahedra in the x = 2 member.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.