Two improved formulations for the minimum latency problem

In network problems, latency is associated with the metric used to evaluate the length of the path from a root vertex to each vertex in the network. In this work we are dealing with two applications or variations of the minimum latency problem known as the repairman problem and the deliveryman problem. We have developed two integer formulations for the minimum latency problem and compared them with other two formulations from the literature for the time-dependent traveling salesman problem. The present work highlights the similarities and differences between the different formulations. In addition, we discuss the convenience of including a set of constraints in order to reduce the computation time needed to reach the optimal solution. We have carried out extensive computational experimentation on asymmetrical instances, since they provide the characteristics of the deliveryman and repairman problems in a better way.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Recombination induced hypergraphs: A new approach to mutation-recombination isomorphism

Natural selection acts on genetic variation that comes from two principal sources: mutation and recombination. Because of the inherent differences between mutation and recombination, it is often assumed that they are qualitatively different ways to explore the genotype space. In this paper a new way of constructing recombination spaces is introduced and the topological features of the resulting hypergraphs are analyzed. It is shown that types which are neighbors in the point mutation space are also neighbors in the recombination space, i.e., mutation and recombination spaces are homomorphic. This implies that the shapes of the fitness functions explored by mutation and recombination are similar. However, the potential of one- and two-point recombination operators to explore the fitness landscape may differ dramatically from uniform recombination operators or mutation operators because of the limited number of recombinant types they can produce. © 1996 John Wiley & Sons, Inc.     

Mechanism of enhanced conversion of 1,2,3-trichloropropane by mutant haloalkane dehalogenase revealed by molecular modeling

1,2,3-Trichloropropane (TCP) is a highly toxic, recalcitrant byproduct of epichlorohydrin manufacture. Haloalkane dehalogenase (DhaA) from Rhodococcus sp. hydrolyses the carbon–halogen bond in various halogenated compounds including TCP, but with low efficiency (k _cat/K _m = 36 s^-1 M^-1). A Cys176Tyr-DhaA mutant with a threefold higher catalytic efficiency for TCP dehalogenation has been previously obtained by error-prone PCR. We have used molecular simulations and quantum mechanical calculations to elucidate the molecular mechanisms involved in the improved catalysis of the mutant, and enantioselectivity of DhaA toward TCP. The Cys176Tyr mutation modifies the protein access and export routes. Substitution of the Cys residue by the bulkier Tyr narrows the upper tunnel, making the second tunnel “slot” the preferred route. TCP can adopt two major orientations in the DhaA enzyme, in one of which the halide-stabilizing residue Asn41 forms a hydrogen bond with the terminal halogen atom of the TCP molecule, while in the other it bonds with the central halogen atom. The differences in these binding patterns explain the preferential formation of the (R)- over the (S)-enantiomer of 2,3-dichloropropane-1-ol in the reaction catalyzed by the enzyme.     

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.     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)     

Asymptotic exponential cones of Metzler matrices and their use in the solution of an algebraic problem

The aim of this paper is that of investigating the asymptotic exponential cone of a single Metzler matrix, introduced in [23], and of defining and analysing the new concept of asymptotic exponential cone of a family of Metzler matrices (along a certain direction). These results will provide necessary and/or sufficient conditions for the solvability of an interesting algebraic problem that arises in the context of continuous-time positive switched systems and, specifically, in the investigation of the reachability property [21,22,25].