3,125 research outputs found
Deterministic Subgraph Detection in Broadcast CONGEST
No full textWe present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation:
- For any constant k, detecting k-paths and trees on k nodes can be done in O(1) rounds.
- For any constant k, detecting k-cycles and pseudotrees on k nodes can be done in O(n)
rounds.
- On d-degenerate graphs, cliques and 4-cycles can be enumerated in O(d + log n) rounds, and
5-cycles in O(d2 + log n) rounds.
In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for d-degenerate graphs can be improved to O(d/logn) and O(d2/logn), respect- ively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique
Improved Approximation Algorithm for <em class="EmphasisTypeItalic">k</em>-level Uncapacitated Facility Location Problem (with Penalties)
No full textWe study the k-level uncapacitated facility location problem (k-level UFL) in which clients need to be connected with paths crossing open facilities of k types (levels). In this paper we first propose an approximation algorithm that for any constant k, in polynomial time, delivers solutions of cost at most αk times OPT, where αk is an increasing function of k, with limk→∞αk=3. Our algorithm rounds a fractional solution to an extended LP formulation of the problem. The rounding builds upon the technique of iteratively rounding fractional solutions on trees (Garg, Konjevod, and Ravi SODA’98) originally used for the group Steiner tree problem. We improve the approximation ratio for k-level UFL for all k ≥ 3, in particular we obtain the ratio equal 2.02, 2.14, and 2.24 for k = 3,4, and 5. Second, we give a simple interpretation of the randomization process (Li ICALP’2011) for 1-level UFL in terms of solving an auxiliary (factor revealing) LP. Armed with this simple view point, we exercise the randomization on our algorithm for the k-level UFL. We further improve the approximation ratio for all k ≥ 3, obtaining 1.97, 2.09, and 2.19 for k = 3,4, and 5. Third, we extend our algorithm to the k-level UFL with penalties (k-level UFLWP), in which the setting is the same as k-level UFL except that the planner has the option to pay a penalty instead of connecting chosen clients.</p
Magnetoresistance in triphenyl-diamine derivative blue organic light emitting devices
No full textCopyright 2008 American Institute of Physics. This article may be downloaded for personal use only. Any other use requires prior permission of the author and the American Institute of Physics. This article appeared in Journal of Applied Physics 103, 043706 (2008) and may be found at
Maize Streak Virus: diversity and virulence
No full textZea mays was first introduced to Africa in Ghana by Portuguese traders in the 16th century. The steady spread of maize cultivation since then has made it the most important cereal crop in Africa today. Whereas improved maize genotypes and agricultural techniques enable yearly yields above 10 tons hectare-1 in the developed world, yearly yields across Africa have remained low at about 1 ton hectare-1 in most countries. Although outmoded agricultural practices are the main reason for poor yields, maize pathogens inflict substantial additional losses. Of the many pathogens currently confronting maize farmers in Africa, Maize streak virus (MSV) is the most significant
Experimental investigations of mastrevirus molecular biology and evolution
No full textIncludes abstract.Includes bibliographical references (leaves 138-161).This dissertation describes three major sets of experiments, all of which involved the construction and use of various reciprocal chimaeric MSV constructs. First, chimaeric viruses were used in genetic complementation-type experiments to investigate the biological significance of interactions between the two virion-sense open reading frames (ORFs) of MSV, their products, and the rest of the genome. Six chimaeric MSV constructs were made by reciprocally exchanging the ORFs encoding movement protein (MP) and coat protein (CP) individually, and in pairs, between MSV-Kom and MSV-Set, which share just 78% overall nucleotide identity. Analysis of symptomatology and infection efficiency of chimaeras and wild-type parental viruses revealed evidence of functionally relevant specific interactions between MSV MP and CP
Short-range structure of liquid palladium and rhodium at very high temperatures
No full textWe performed X-ray absorption spectroscopy experiments at the Pd and Rh K-edges of solid and liquid samples. The measurements were performed at 1850 K for liquid Pd and at 2240 K for liquid Rh. The short range shape of the radial distribution function is derived and compared for both the liquid and solid phases. These results provide a severe test for proposed interaction potentials suitable to describe these metallic melts. (C) 1999 Elsevier Science B.V. All rights reserved
An Improved Approximation Algorithm for the Hard Uniform Capacitated k-median Problem
No full textIn the k-median problem, given a set of locations, the goal is to select a subset of at most k centers so as to minimize the total cost of connecting each location to its nearest center. We study the uniform hard capacitated version of the k-median problem, in which each selected center can only serve a limited number of locations.
Inspired by the algorithm of Charikar, Guha, Tardos and Shmoys,
we give an improved approximation algorithm for this problem with increasing the capacities by a constant factor, which improves the previous best approximation algorithm proposed by Byrka, Fleszar, Rybicki and Spoerhase
Influence of hydrogen reduction on the structure of PbSiO3 glass: an EXAFS study
No full textA new X-ray analysis of the structure of lead-silicate glass PbSiO3, and of its hydrogen-reduced form, is presented. The X-ray absorption spectroscopy (XAS) experiments were performed at the L-3-edge of Pb, and the data have been analyzed in the framework of the multiple scattering (MS) theory. The influence of the reduction time on the glass structure is presented. In unreduced glass the Pb atom neighborhood resembles the corresponding local ordering in red PbO. On increasing the reduction time Pb neighborhood becomes more and more similar to that of fee lead, which is compatible with the experimentally observed creation of metallic lead granules. (C) 2000 Elsevier Science B.V. All rights reserved
The structure of porous and spontaneously densified amorphous PbSiO3: a molecular dynamics study
No full textIn the paper we propose and test a "gel-drying" method of obtaining porous oxide glasses in Molecular Dynamics (MD) simulations. The simulation is started with
low (screened) values of ionic charges. Then,
the charges are gradually increased (to mimic the
gradually elimination of a polar solvent) up
to full ionic charges (a completely dry gel).
This computational trick is applied to produce a porous PbSiO3 system.
The structure of the resulting low-density samples is analysed in detail.
Then, the porous structures are submitted to spontaneous densification, and the structure
of the obtained dense bulk glasses id analysed. Finally,the structures of bulk glass obtained via
spontaneous densification (density p=8250kg/m3) and bulk glass
of the same density obtained via isotropic compression are compared
- …
