On a Polynomial Fractional Formulation for Independence Number of a Graph

In this paper we characterize the local maxima of a continuous global optimization formulation for finding the independence number of a graph. Classical Karush-Kuhn-Tucker conditions and simple combinatorial arguments are found sufficient to deduce several interesting properties of the local and global maxima. These properties can be utilized in developing new approaches to the maximum independent set problem.     

Theoretical conformational analysis of some agonists of the H1- and H2-receptors of histamine

The conformational equilibrium of -(aminoethyl)pyridines has been studied by molecular-mechanics using the geometry optimization. It has been determined that the equilibrium is characterized by the nearly statistical distribution of the ap- and sc-conformers about the bond. Substitution of the dimethylamino-group for the amino-group results in a slight shift of the equilibrium toward the ap-rotamers. The global minimum in -(ammoniumethyl)pyridines corresponds to the conformation with the +sc-orientation about the central C-C bond and the -sc-orientation (in the case of the dimethylammonium derivatives) about the bond. In the latter conformation, the bond of the ammonium group is oriented toward the pyridine cycle. For charged compounds, the regular orthogonal conformation of the aromatic-ring plate is distorted (the vicinal C-C bond becomes eclipsed).Translated from Izvestiya Akademii Nauk SSSR, Seriya Khimicheskaya, No. 8, pp. 1833–1840, August, 1991.The authors are grateful to P. P. Shagidullin and A. Kh. Plyamovatyi for their interest in this work and for fruitful discussions.     

Molecular structure of ortho-nitrobenzyltriethylammonium bromide

It was established by x-ray crystallographic analysis that the molecular o-nitrobenzyltriethylammonium cation has an orthogonal orientation of the benzene ring and the vicinal C-N⁺ bond (=93.8°). The nitro group deviates from the plane of the aromatic ring by an angle of 26.9°. One of the ethyl groups at the quaternary nitrogen atom is in an ap-conformation (=176.2°); the other two are in sc-conformations, characterized by torsional angles 65.1 and 69.4°.Translated from Izvestiya Akademii Nauk SSSR, Seriya Khimicheskaya, No. 8, pp. 1816–1818, August, 1991.     

On clique relaxation models in network analysis

Increasing interest in studying community structures, or clusters in complex networks arising in various applications has led to a large and diverse body of literature introducing numerous graph-theoretic models relaxing certain characteristics of the classical clique concept. This paper analyzes the elementary clique-defining properties implicitly exploited in the available clique relaxation models and proposes a taxonomic framework that not only allows to classify the existing models in a systematic fashion, but also yields new clique relaxations of potential practical interest. Some basic structural properties of several of the considered models are identified that may facilitate the choice of methods for solving the corresponding optimization problems. In addition, bounds describing the cohesiveness properties of different clique relaxation structures are established, and practical implications of choosing one model over another are discussed.     

Photoelectrochromic Organic Systems

Russian Journal of General Chemistry - The electrochemical properties of photochromic compounds from the classes of diarylethenes, fulgides, quinones, spiropyrans, and dihydropyrenes exhibiting...     

New Beam Lines for Applied Research at the NICA Facility and Their Beam Dynamics

Physics of Particles and Nuclei Letters - A new accelerator complex with new beam lines for applied research is being constructed at the Joint Institute for Nuclear Research (Dubna, Russia) as part...     

Stereo- and regioselectivity of the catalytic system MoCl5/SiO2-SnMe4 in the reaction of metathesis and cometathesis of olefins and their functional derivatives

It was shown that the catalytic system MoCl₅/SiO₂-SnMe₄ has almost 100% regioselectivity with respect to olefins. The stereoselectivity of the system is not a function of the length of the -olefin chain, temperature, or addition of functional groups (COOEt, Cl). Addition of pentachlorophenoxy and 8-hydroxyquinolyl ligands significantly reduces the activity of the catalytic system with a slight increase in the stereoselectivity with respect to the cis-isomer.Translated from Izvestiya Akademii Nauk SSSR, Seriya Khimicheskaya, No. 1, pp. 168–171, January, 1990.     

On connected dominating sets of restricted diameter

A connected dominating set (CDS) is commonly used to model a virtual backbone of a wireless network. To bound the distance that information must travel through the network, we explicitly restrict the diameter of a CDS to be no more than s leading to the concept of a dominating s-club. We prove that for any fixed positive integer s it is NP-complete to determine if a graph has a dominating s  -club, even when the graph has diameter s+1$s+1$. As a special case it is NP-complete to determine if a graph of diameter two has a dominating clique. We then propose a compact integer programming formulation for the related minimization problem, enhance the approach with variable fixing rules and valid inequalities, and present computational results.     

Solving maximum clique in sparse graphs: an O(nm+n2^{d/4}) algorithm for d-degenerate graphs

We describe an algorithm for the maximum clique problem that is parameterized by the graph’s degeneracy \(d\) . The algorithm runs in \(O\left( nm+n T_d \right) \) time, where \(T_d\) is the time to solve the maximum clique problem in an arbitrary graph on \(d\) vertices. The best bound as of now is \(T_d=O(2^{d/4})\) by Robson. This shows that the maximum clique problem is solvable in \(O(nm)\) time in graphs for which \(d \le 4 \log _2 m + O(1)\) . The analysis of the algorithm’s runtime is simple; the algorithm is easy to implement when given a subroutine for solving maximum clique in small graphs; it is easy to parallelize. In the case of Bianconi-Marsili power-law random graphs, it runs in \(2^{O(\sqrt{n})}\) time with high probability. We extend the approach for a graph invariant based on common neighbors, generating a second algorithm that has a smaller exponent at the cost of a larger polynomial factor.     

Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations

Given a simple undirected graph, the problem of finding a maximum subset of vertices satisfying a nontrivial, interesting property Π that is hereditary on induced subgraphs, is known to be NP-hard. Many well-known graph properties meet the above conditions, making the problem widely applicable. This paper proposes a general purpose exact algorithmic framework to solve this problem and investigates key algorithm design and implementation issues that are helpful in tailoring the general framework for specific graph properties. The performance of the algorithms so derived for the maximum s-plex and the maximum s-defective clique problems, which arise in network-based data mining applications, is assessed through a computational study.