Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm

This paper proposes a hybrid self-adaptive evolutionary algorithm for graph coloring that is hybridized with the following novel elements: heuristic genotype-phenotype mapping, a swap local search heuristic, and a neutral survivor selection operator. This algorithm was compared with the evolutionary algorithm with the SAW method of Eiben et al., the Tabucol algorithm of Hertz and de Werra, and the hybrid evolutionary algorithm of Galinier and Hao. The performance of these algorithms were tested on a test suite consisting of randomly generated 3-colorable graphs of various structural features, such as graph size, type, edge density, and variability in sizes of color classes. Furthermore, the test graphs were generated including the phase transition where the graphs are hard to color. The purpose of the extensive experimental work was threefold: to investigate the behavior of the tested algorithms in the phase transition, to identify what impact hybridization with the DSatur traditional heuristic has on the evolutionary algorithm, and to show how graph structural features influence the performance of the graph-coloring algorithms. The results indicate that the performance of the hybrid self-adaptive evolutionary algorithm is comparable with, or better than, the performance of the hybrid evolutionary algorithm which is one of the best graph-coloring algorithms today. Moreover, the fact that all the considered algorithms performed poorly on flat graphs confirms that graphs of this type are really the hardest to color.     

Paths through inverse limits

In Bani?, ?repnjak, Merhar and Milutinovi? (2010) [2] the authors proved that if a sequence of graphs of surjective upper semi-continuous set-valued functions fn:X→X² converges to the graph of a continuous single-valued function f:X→X, then the sequence of corresponding inverse limits obtained from fn converges to the inverse limit obtained from f. In this paper a more general result is presented in which surjectivity of fn is not required. The result is also generalized to the case of inverse sequences with non-constant sequences of bonding maps. Finally, these new theorems are applied to inverse limits with tent maps. Among other applications, it is shown that the inverse limits appearing in the Ingram conjecture (with a point added) form an arc.     

The security number of lexicographic products

A subset S of vertices of a graph G is a secure set if |N [X] ∩ S| ≥ |N [X] ? S| holds for any subset X of S, where N [X] denotes the closed neighborhood of X. The minimum cardinality s(G) of a secure set in G is called the security number of G. We investigate the security number of lexicographic product graphs by defining a new concept of tightly-securable graphs. In particular we derive several exact results for different families of graphs which yield some general results.     

NZ‐flows in strong products of graphs

We prove that the strong product G₁? G₂ of G₁ and G₂ is ?₃‐flow contractible if and only if G₁? G₂ is not T? K₂, where T is a tree (we call T? K₂ a K₄‐tree). It follows that G₁? G₂ admits an NZ 3 ‐flow unless G₁? G₂ is a K₄ ‐tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3‐flow if G₁? G₂ is not a K₄ ‐tree, and an NZ 4‐flow otherwise. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010     

Travel time models for automated warehouses with aisle transferring storage and retrieval machine

This paper presents analytical travel time models for the computation of travel time for automated warehouses with the aisle transferring S/R machine (in continuation multi-aisle AS/RS). These models consider the operating characteristics of the storage and retrieval machine such as acceleration and deceleration and the maximum velocity. Assuming uniform distributed storage rack locations and pick aisles and using the probability theory, the expressions of the cumulative distribution functions with which the mean travel time is calculated, have been determined. The computational models enable the calculation of the mean travel time for the single and dual command cycles, from which the performance of multi-aisle AS/RS can be evaluated. A simulation model of multi-aisle AS/RS has been developed to compare the performances of the proposed analytical travel time models. The analyses show that regarding all examined types of multi-aisle AS/RS, the results of proposed analytical travel time models correlate with the results of simulation models of multi-aisle AS/RS.     

Quantum phase transition in a far-from-equilibrium steady state of an XY spin chain

Using quantization in the Fock space of operators, we compute the nonequilibrium steady state in an open Heisenberg XY spin 1/2 chain of a finite but large size coupled to Markovian baths at its ends. Numerical and theoretical evidence is given for a far-from-equilibrium quantum phase transition with the spontaneous emergence of long-range order in spin-spin correlation functions, characterized by a transition from saturation to linear growth with the size of the entanglement entropy in operator space.     

Structural diversity of isothiocyanato Cd(II) and Zn(II) Girard’s T hydrazone complexes in solution and solid state: effect of H-bonding on coordination number and supramolecular assembly of Cd(II) complex in solid state

The isothiocyanato Zn(II) complex (1) and mixed isothiocyanato/thiocyanato Cd(II) complex (2) with the condensation product of 2-acetylpyridine and trimethylammoniumacetohydrazide chloride (Girard’s T reagent) (HLCl) were investigated both experimentally and theoretically. The crystal structures of both complexes showed tridentate N₂O coordination of hydrazine ligand. In complex 1 square-pyramidal coordination surrounding of Zn(II) consists of deprotonated hydrazone ligand and two isothiocyanato ligands, while in octahedral Cd(II) complex ligand is coordinated without deprotonation as a positively charged species and coordination geometry is completed with two N-coordinated and one S-coordinated NCS^? anions. NMR spectroscopy and molar conductivity results for Cd(II) and Zn(II) complexes indicated their instability in solution. DFT calculations were performed to explain coordination preference and stability of complexes 1 and 2 in solid state and in solution. The obtained Cd(II) complex is the first reported mononuclear pseudohalide/halide Cd(II) complex with quinoline-/pyridine-based hydrazone ligands possessing octahedral geometry in solid state. In this complex, H-bonding has significant impact on coordination number and supramolecular assembly in solid state.     

An extraction system for low-energy hydrogen ions formed by electron impact

A system has been developed for extracting near-zero kinetic energy H⁻ and D⁻ ions formed by dissociative electron attachment. It is the essential part of a new set-up for vibrational spectroscopy of hydrogen molecules. A magnetic field is used to collimate the probing electron beam. Ions produced by electron collision with the target molecules are collected by the combined action of this field and an electrostatic field penetrating into the interaction region. Highly effective extraction is achieved by taking into account the correct out-of plane displacement of ion trajectories which is usually neglected in similar arrangements. The extraction conditions are mass dependent so that by proper tuning, mass selection of detected ions is achieved. The new system is also used for detecting positive ions created by electron collisions with hydrogen atoms and molecules.