Computing hyperbolic choreographies

An algorithm is presented for numerical computation of choreographies in spaces of constant negative curvature in a hyperbolic cotangent potential, extending the ideas given in a companion paper [14] for computing choreographies in the plane in a Newtonian potential and on a sphere in a cotangent potential. Following an idea of Diacu, Pérez-Chavela and Reyes Victoria [9], we apply stereographic projection and study the problem in the Poincaré disk. Using approximation by trigonometric polynomials and optimization methods with exact gradient and exact Hessian matrix, we find new choreographies, hyperbolic analogues of the ones presented in [14]. The algorithm proceeds in two phases: first BFGS quasi-Newton iteration to get close to a solution, then Newton iteration for high accuracy.     

Implementing an efficient fptas for the 0–1 multi-objective knapsack problem

In the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0–1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well.     

A shortest path-based approach to the multileaf collimator sequencing problem

The multileaf collimator sequencing problem is an important component in effective cancer treatment delivery. The problem can be formulated as finding a decomposition of an integer matrix into a weighted sequence of binary matrices whose rows satisfy a consecutive ones property. Minimising the cardinality of the decomposition is an important objective and has been shown to be strongly NP-hard, even for a matrix restricted to a single column or row. We show that in this latter case it can be solved efficiently as a shortest path problem, giving a simple proof that the one-row problem is fixed-parameter tractable in the maximum intensity. We develop new linear and constraint programming models exploiting this result. Our approaches significantly improve the best known for the problem, bringing real-world sized problem instances within reach of exact algorithms.     

Trees with Given Stability Number and Minimum Number of Stable Sets

We study the structure of trees minimizing their number of stable sets for given order n and stability number α. Our main result is that the edges of a non-trivial extremal tree can be partitioned into n ? α stars, each of size \({\lceil\frac{n-1}{n-\alpha}\rceil}\) or \({\lfloor\frac{n-1}{n-\alpha}\rfloor}\) , so that every vertex is included in at most two distinct stars, and the centers of these stars form a stable set of the tree.     

Transmetalation of a nucleophilic carbene fragment: from early to late transition metals

Early transition metal nucleophilic carbene complexes have been used as stoichiometric carbene transfer agents in a transmetalation process.     

Periodic density functional theory investigation of the uranyl ion sorption on the TiO2 rutile (110) face

Periodic density functional theory calculations have been performed in order to study the uranyl ion sorption on the TiO2 rutile (110) face. From experimental measurements, two uranyl surface complexes have been observed and the two corresponding sorption sites have been identified. However, from a crystallographic point of view, three different sorption sites can be considered on this face. The corresponding three surface bidentate complexes were modeled and optimized, and their relative energies were calculated. Only 5 kJ/mol separates the two most stable structures, which correspond to the experimental ones. The third surface complex is nearly 10 kJ/mol less stable, in agreement with the fact that it was not observed experimentally.     

Variable neighborhood search for extremal graphs. 6. Analyzing bounds for the connectivity index

Recently, Araujo and De la Pe?a gave bounds for the connectivity index of chemical trees as a function of this index for general trees and the ramification index of trees. They also gave bounds for the connectivity index of chemical graphs as a function of this index for maximal subgraphs which are trees and the cyclomatic number of the graphs. The ramification index of a tree is first shown to be equal to the number of pending vertices minus 2. Then, in view of extremal graphs obtained with the system AutoGraphiX, all bounds of Araujo and De la Pe?a are improved, yielding tight bounds, and in one case corrected. Moreover, chemical trees of a given order and a number of pending vertices with minimum and with maximum connectivity index are characterized.     

Facet defining inequalities among graph invariants: The system GraPHedron

We present a new computer system, called GraPHedron, which uses a polyhedral approach to help the user to discover optimal conjectures in graph theory. We define what should be optimal conjectures and propose a formal framework allowing to identify them. Here, graphs with n nodes are viewed as points in the Euclidian space, whose coordinates are the values of a set of graph invariants. To the convex hull of these points corresponds a finite set of linear inequalities. These inequalities computed for a few values of n can be possibly generalized automatically or interactively. They serve as conjectures which can be considered as optimal by geometrical arguments.We describe how the system works, and all optimal relations between the diameter and the number of edges of connected graphs are given, as an illustration. Other applications and results are mentioned, and the forms of the conjectures that can be currently obtained with GraPHedron are characterized.