An exact algorithm for the capacitated shortest spanning arborescence

We are given a complete and loop-free digraphG=(V, A), whereV={1,...,n} is the vertex set,A={(i, j) :i, j V} the arc set, andr V is a distinguishedroot vertex. For each arc (i, j) A, letc _ij be the associatedcost, and for each vertexi, letq _i 0 be the associateddemand (withq _r =0). Moreover, a nonnegativebranch capacity, Q, is defined.A Capacitated Shortest Spanning Arborescence rooted at r (CSSA _r ) is a minimum cost partial digraph such that: (i) each vertexj r has exactly one entering arc; (ii) for each vertexj r, a path fromr toj exists; (iii) for each branch leaving vertexr, the total demand of the vertices does not exceed the branch capacity,Q. A variant of theCSSA _r problem (calledD-CSSA _r ) arises when the out-degree of the root vertex is constrained to be equal to a given valueD. These problems are strongly NP-hard, and find practical applications in routing and network design. We describe a new Lagrangian lower bound forCSSA _r andD-CSSA _r problems, strengthened in a cutting plane fashion by iteratively adding violated constraints to the Lagrangian problem. We also present a new lower bound based on projection leading to the solution of min-cost flow problems. The two lower bounds are then combined so as to obtain an overall additive lower bounding procedure. The additive procedure is then imbedded in a branch-and-bound algorithm whose performance is enhanced by means of reduction procedures, dominance criteria, feasibility checks and upper bounding. Computational tests on asymmetric and symmetric instances from the literature, involving up to 200 vertices, are given, showing the effectiveness of the proposed approach.     

Diffraction engineering in arrays of photonic crystal waveguides

Light propagation in uniform arrays of photonic crystal waveguides is studied. We demonstrate that, in stark contrast to the case of conventional waveguide arrays, diffraction can be tailored both in magnitude and sign by varying only the spacing between adjacent waveguides. Diffraction management in ultracompact arrays of straight photonic crystal waveguides is demonstrated by solving Maxwell's equations through the time-domain finite-element method.     

Alkylation of nucleic acids by the antitumor agent COMC

[reaction: see text]. Mass spectral data are presented indicating that the antitumor agent 2-crotonyloxymethyl-2-cyclohexenone (COMC) is capable of alkylating oligonucleotides via a mechanism involving an electrophilic exocyclic enone intermediate. Under physiological conditions, the exocyclic enone is likely the glutathionylated 2-exomethylenecyclohexenone. This supports a recent hypothesis that the antitumor activity of COMC arises from alkylation of nucleic acids and/or proteins critical to cell function and not from competitive inhibition of glyoxalase I by an adduct of COMC and glutathione.     

Nucleophilic addition of the thiocyanate ion to ferrocenyl-stabilised carbocations

The reaction of ferrocenylmethylcarbocations with the ambident thiocyanate ion produces only the isothiocyanate isomer.     

A lower bound for the complexity of Craig's interpolants in sentential logic

For any sentenceα (in sentential logic) letd _α be the delay complexity of the boolean functionf _α represented byα. We prove that for infinitely manyd (and starting with somed<620) there exist valid implicationsα→β withd _α,d _β≦d such that any Craig's interpolantx has its delay complexityd _χ greater thand+(1/3)·log(d/2). This is the first (non-trivial) known lower bound on the complexity of Craig's interpolants in sentential logic, whose general study may well have an impact on the central problems of computation theory.     

Probing fragment complementation by rigid-body docking: in silico reconstitution of calbindin D9k

Fragment complementation is gaining an increasing impact as a nonperturbing method to probe noncovalent interactions within protein supersecondary structures. In this study, the fast Fourier transform rigid-body docking algorithm ZDOCK has been employed for in silico reconstitution of the calcium binding protein calbindin D9k, from its two EF-hands subdomains, namely, EF1 (residues 1-43) and EF2 (residues 44-75). The EF1 fragment has been used both in its wild type and in nine mutant forms, in line with in vitro experiments. Consistent with in vitro data, ZDOCK reconstituted the proper fold of wild-type and mutated calbindin, locating the nativelike structures (i.e., holding a root-mean-square deviation < 1 A with respect to the X-ray structure) among the first 10 top-scored solutions out of 4000. Moreover, the three independent in silico reconstitutions of wild-type calbindin ranked a nativelike structure at the top of the output list, that is, the best scored one. The algorithm has been also successfully challenged in reconstituting the EF2 homodimer from two identical copies of the monomer. Furthermore, quantitative models consisting of linear correlations between thermodynamic data and ZDOCK scores were built, providing a tested tool for very fast in silico predictions of the free energy of association of protein-protein complexes solved at the atomic level and known to not undergo significant conformational changes upon binding.     

Partially dynamic maintenance of minimum weight hyperpaths

We address the problem of dynamically maintaining minimum weight hyperpaths in a directed hypergraph in a decremental setting. For such a problem, we provide a new efficient algorithm that works for a wide class of hyperpath weight measures. This algorithm explicitly updates minimum weight hyperpaths in

Full-size image

worst case time under a sequence of L hyperarc weight increments and hyperarc deletions, where C is the maximum weight of minimum hyperpaths in and is the size of the representation of the hypergraph. Hyperpath weight measures are only required to belong to the class of strict weakly superior functions.     

Nonlinear unbalanced bessel beams: stationary conical waves supported by nonlinear losses

Nonlinear losses accompanying self-focusing substantially impact the dynamic balance of diffraction and nonlinearity, permitting the existence of localized and stationary solutions of the 2D + 1 nonlinear Schr?dinger equation, which are stable against radial collapse. These are featured by linear, conical tails that continually refill the nonlinear, central spot. An experiment shows that the discovered solution behaves as a strong attractor for the self-focusing dynamics in Kerr media.