On the effects of geographical constraints on task execution in complex

In the present work, the effects of spatial constraints on the efficiency of task execution in systems underlain by geographical complex networks are investigated, where the probability of connection decreases with the distance between the nodes. The investigation considers several configurations of the parameters defining the network connectivity, and the Barabasi-Albert network model is also considered for comparisons. The results show that the effect of connectivity is significant only for shorter tasks, the locality of connection simplied by the spatial constraints reduces efficiency, and the addition of edges can improve the efficiency of the execution, although with increasing locality of the connections the improvement is small.

Fast long-range connections in transportation networks

Multidimensional scaling is applied in order to visualize an analogue of the small-world effect implied by edges having different displacement velocities in transportation networks. Our findings are illustrated for two real-world systems, namely the London urban network (streets and underground) and the US highway network enhanced by some of the main US airlines routes. We also show that the travel time in these two networks is drastically changed by attacks targeting the edges with large displacement velocities. (C) 2011 Elsevier By. All rights reserved.

Identifying the borders of mathematical knowledge

Based on a divide and conquer approach, knowledge about nature has been organized into a set of interrelated facts, allowing a natural representation in terms of graphs: each `chunk` of knowledge corresponds to a node, while relationships between such chunks are expressed as edges. This organization becomes particularly clear in the case of mathematical theorems, with their intense cross-implications and relationships. We have derived a web of mathematical theorems from Wikipedia and, thanks to the powerful concept of entropy, identified its more central and frontier elements. Our results also suggest that the central nodes are the oldest theorems, while the frontier nodes are those recently added to the network. The network communities have also been identified, allowing further insights about the organization of this network, such as its highly modular structure.

Synthesis, Infrared Spectroscopy and Crystal Structure Determination of a New Decavanadate

Synthesis, infrared spectroscopy and crystal structure of a new potassium decavanadate decahydrate, K(6)[V(10)O(28)] 10H(2)O, has been reported The infrared spectrum is dominated by decavanadate polyanion and water bands The X-ray crystallography analysis found the compound crystallizes in a triclinic system with the parameters a = 10 5334 (4) angstrom, b = 10 6600 (4) angstrom, c = 17 7351 (5) angstrom, alpha = 76 940 (2)degrees, beta = 75 836 (2)degrees, gamma = 64 776 (2)degrees, V = 1,729 86 (11) A(3), Z = 2, space group P (1) over bar The polyanion consists of ten [VO(6)] octahedra sharing edges, in which the V-O distances are in good agreement with those reported for other decavanadates The crystal structure is stabilized by potassium cations and water molecules forming a complex pattern of hydrogen bonding and short contact ionic interactions

Rankamaite from the Urubu pegmatite, Itinga, Minas Gerais, Brazil: Crystal chemistry and Rietveld refinement

A new occurrence of rankamaite is here described at the Urubu pegmatite, Itinga municipality, Minas Gerais, Brazil. The mineral forms cream-white botryoidal aggregates of acicular to fibrous crystals, intimately associated with simpsonite, thoreaulite, cassiterite, quartz, elbaite, albite, and muscovite. The average of six chemical analyses obtained by electron microprobe is (range in parentheses, wt%): Na(2)O 2.08 (1.95-2.13), K(2)O 2.61 (2.52-2.74), Al(2)O(3) 1.96 (1.89-2.00), Fe(2)O(3) 0.01 (0.00-0.03), TiO(2) 0.02 (0.00-0.06), Ta(2)O(5) 81.04 (79.12-85.18), Nb(2)O(5) 9.49 (8.58-9.86), total 97.21 (95.95-101.50). The chemical formula derived from this analysis is (Na(1.55)K(1.28))(Sigma 2.83)(Ta(8.45)Nb(1.64)Al(0.89)Fe(0.01)(3+)Ti(0.01))(Sigma 11.00)[O(25.02)(OH)(5.98)](Sigma 31.00). Rankamaite is an orthorhombic ""tungsten bronze"" (OTB), crystallizing in the space group Cmmm. Its unit-cell parameters refined from X-ray diffraction powder data are: a = 17.224(3), b = 17.687(3), c = 3.9361(7) angstrom, V = 1199.1(3) angstrom(3), Z = 2. Rietveld refinement of the powder data was undertaken using the structure of LaTa(5)O(14) as a starting model for the rankamaite structure. The structural formula obtained with the Rietveld analyses is: (Na(2.21)K(1.26))Sigma(3.37)(Ta(9.12)NB(1.30) Al(0.59))(Sigma 11.00)[O(26.29)(OH)(4.71)](Sigma 31.00). The tantalum atoms are coordinated by six and seven oxygen atoms in the form of distorted TaO(6) octahedra and TaO(2) pentagonal bipyramids, respectively. Every pentagonal bipyramid shares edges with four octahedra, thus forming Ta(5)O(14) units. The potassium atom is in an 11-fold coordination, whereas one sodium atom is in a 10-fold and the other is in a 12-fold coordination. Raman and infrared spectroscopy were used to investigate the room-temperature spectra of rankamaite.

Lycopodiopsis derbyi Renault from the Corumbatai Formation in the state of Sao Paulo (Guadalupian of Parana Basin, Southern Brazil): New data from compressed silicified stems

Lycopodiopsis derbyi Renault was analyzed on the basis of compressed silicified stems from four Guadalupian outcrops of the Parana Basin (Corumbatai Formation) in the State of Sao Paulo, Southern Brazil. Dichotomous stems have been recorded, and three different branch regions related to apoxogenesis are described. The most proximal region has larger, clearly rhomboidal leaf cushions, with protruding upper edges; the intermediate transitional region also has rhombic leaf cushions, but they are smaller and less elongated than the lower in the same axis; finally, the most distal region reveals only incipient cushions, with inconspicuous infrafoliar bladders; interspersed microphylls were still attached. A well preserved branch representative of this most distal region was sectioned; it has a siphonostelic cylinder similar to that previously described for L derbyi. The cortex, however, shows new traits, such as a short portion of elongated cells between the periderm and the external cortex (or leaf cushion tissue). The stems were apparently silicified prior to their final burial but were probably not transported for long distances. Their final burial may have taken place during storm events, which were common during the deposition of the Corumbatai Formation. These stems are commonly deformed due to compression, mainly because the internal cortical portions rapidly decayed prior to silicification due to their thin-walled tissue, and are therefore not preserved. The common alkalinity of a shallow marine environment such as that in which the Corumbatai Formation was deposited, should mobilize the silica and favors petrifaction. Based on the new data, an emended diagnosis is proposed and a modification of the identification key published by Thomas and Meyen in 1984 for Upper Paleozoic Lycopsida is suggested. (C) 2009 Elsevier B.V. All rights reserved.

PARALLEL ALGORITHMS FOR MAXIMAL CLIQUES IN CIRCLE GRAPHS AND UNRESTRICTED DEPTH SEARCH

We present parallel algorithms on the BSP/CGM model, with p processors, to count and generate all the maximal cliques of a circle graph with n vertices and m edges. To count the number of all the maximal cliques, without actually generating them, our algorithm requires O(log p) communication rounds with O(nm/p) local computation time. We also present an algorithm to generate the first maximal clique in O(log p) communication rounds with O(nm/p) local computation, and to generate each one of the subsequent maximal cliques this algorithm requires O(log p) communication rounds with O(m/p) local computation. The maximal cliques generation algorithm is based on generating all maximal paths in a directed acyclic graph, and we present an algorithm for this problem that uses O(log p) communication rounds with O(m/p) local computation for each maximal path. We also show that the presented algorithms can be extended to the CREW PRAM model.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Minimum cycle cover and Chinese postman problems on mixed graphs with bounded tree-width

Let M = (V, E, A) be a mixed graph with vertex set V, edge set E and arc set A. A cycle cover of M is a family C = {C(1), ... , C(k)} of cycles of M such that each edge/arc of M belongs to at least one cycle in C. The weight of C is Sigma(k)(i=1) vertical bar C(i)vertical bar. The minimum cycle cover problem is the following: given a strongly connected mixed graph M without bridges, find a cycle cover of M with weight as small as possible. The Chinese postman problem is: given a strongly connected mixed graph M, find a minimum length closed walk using all edges and arcs of M. These problems are NP-hard. We show that they can be solved in polynomial time if M has bounded tree-width. (C) 2008 Elsevier B.V. All rights reserved.

Sparse partition universal graphs for graphs of bounded degree

In 1983, Chvatal, Trotter and the two senior authors proved that for any Delta there exists a constant B such that, for any n, any 2-colouring of the edges of the complete graph K(N) with N >= Bn vertices yields a monochromatic copy of any graph H that has n vertices and maximum degree Delta. We prove that the complete graph may be replaced by a sparser graph G that has N vertices and O(N(2-1/Delta)log(1/Delta)N) edges, with N = [B`n] for some constant B` that depends only on Delta. Consequently, the so-called size-Ramsey number of any H with n vertices and maximum degree Delta is O(n(2-1/Delta)log(1/Delta)n) Our approach is based on random graphs; in fact, we show that the classical Erdos-Renyi random graph with the numerical parameters above satisfies a stronger partition property with high probability, namely, that any 2-colouring of its edges contains a monochromatic universal graph for the class of graphs on n vertices and maximum degree Delta. The main tool in our proof is the regularity method, adapted to a suitable sparse setting. The novel ingredient developed here is an embedding strategy that allows one to embed bounded degree graphs of linear order in certain pseudorandom graphs. Crucial to our proof is the fact that regularity is typically inherited at a scale that is much finer than the scale at which it is assumed. (C) 2011 Elsevier Inc. All rights reserved.

Inferring Contagion in Regulatory Networks

Several gene regulatory network models containing concepts of directionality at the edges have been proposed. However, only a few reports have an interpretable definition of directionality. Here, differently from the standard causality concept defined by Pearl, we introduce the concept of contagion in order to infer directionality at the edges, i.e., asymmetries in gene expression dependences of regulatory networks. Moreover, we present a bootstrap algorithm in order to test the contagion concept. This technique was applied in simulated data and, also, in an actual large sample of biological data. Literature review has confirmed some genes identified by contagion as actually belonging to the TP53 pathway.

The 3-colored Ramsey number of even cycles

Denote by R(L, L, L) the minimum integer N such that any 3-coloring of the edges of the complete graph on N vertices contains a monochromatic copy of a graph L. Bondy and Erdos conjectured that when L is the cycle C(n) on n vertices, R(C(n), C(n), C(n)) = 4n - 3 for every odd n > 3. Luczak proved that if n is odd, then R(C(n), C(n), C(n)) = 4n + o(n), as n -> infinity, and Kohayakawa, Simonovits and Skokan confirmed the Bondy-Erdos conjecture for all sufficiently large values of n. Figaj and Luczak determined an asymptotic result for the `complementary` case where the cycles are even: they showed that for even n, we have R(C(n), C(n), C(n)) = 2n + o(n), as n -> infinity. In this paper, we prove that there exists n I such that for every even n >= n(1), R(C(n), C(n), C(n)) = 2n. (C) 2009 Elsevier Inc. All rights reserved.

Asymmetric Ramsey Properties of Random Graphs Involving Cliques

Consider the following problem: Forgiven graphs G and F(1),..., F(k), find a coloring of the edges of G with k colors such that G does not contain F; in color i. Rodl and Rucinski studied this problem for the random graph G,,, in the symmetric case when k is fixed and F(1) = ... = F(k) = F. They proved that such a coloring exists asymptotically almost surely (a.a.s.) provided that p <= bn(-beta) for some constants b = b(F,k) and beta = beta(F). This result is essentially best possible because for p >= Bn(-beta), where B = B(F, k) is a large constant, such an edge-coloring does not exist. Kohayakawa and Kreuter conjectured a threshold function n(-beta(F1,..., Fk)) for arbitrary F(1), ..., F(k). In this article we address the case when F(1),..., F(k) are cliques of different sizes and propose an algorithm that a.a.s. finds a valid k-edge-coloring of G(n,p) with p <= bn(-beta) for some constant b = b(F(1),..., F(k)), where beta = beta(F(1),..., F(k)) as conjectured. With a few exceptions, this algorithm also works in the general symmetric case. We also show that there exists a constant B = B(F,,..., Fk) such that for p >= Bn(-beta) the random graph G(n,p) a.a.s. does not have a valid k-edge-coloring provided the so-called KLR-conjecture holds. (C) 2008 Wiley Periodicals, Inc. Random Struct. Alg., 34, 419-453, 2009

Ethanol steam reforming for production of hydrogen on magnesium aluminate-supported cobalt catalysts promoted by noble metals

The performance of noble metal (Pt, Ru, Ir)-promoted Co/MgAl(2)O(4) catalysts for the steam reforming of ethanol was investigated. The catalysts were characterized by energy-dispersive X-ray spectroscopy, Xray diffraction, UV-vis diffuse reflectance spectroscopy, temperature-programmed reduction, temperature-programmed oxidation and X-ray absorption near edge structure (XANES). The results showed that the formation of inactive cobalt aluminate was suppressed by the presence of a MgAl(2)O(4) spinel phase. The effects of the noble metals included a marked lowering of the reduction temperatures of the cobalt surface species interacting with the support. It was seen that the addition of noble metal stabilized the Co sites in the reduced state throughout the reaction. Catalytic performance was enhanced in the promoted catalysts, particularly CoRu/MgAl(2)O(4), which showed the highest selectivity for H(2) production. (C) 2009 Elsevier B.V. All rights reserved.