Approximating the traffic grooming problem

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most g of them (g being the grooming factor) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADMs, one at each endpoint, and in case g lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving g−1 ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for g=1 and for a general g. Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for g=1. We present an approximation algorithm for this problem. For every value of g the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies—including the ring topology—is shown to be 2lng+o(lng). This is the first approximation algorithm for the grooming problem with a general grooming factor g.     

Optimal first- to sixth-order accurate Runge-Kutta schemes

An optimal choice of free parameters in explicit Runge-Kutta schemes up to the sixth order is discussed. A sixth-order seven-stage scheme that is immediately ahead of Butcher’s second barrier is constructed. The study is performed in the most general form, and its results are applicable to both autonomous and nonautonomous problems.     

Acyclic edge colorings of graphs

A proper coloring of the edges of a graph G is called acyclic if there is no 2‐colored cycle in G. The acyclic edge chromatic number of G, denoted by a′(G), is the least number of colors in an acyclic edge coloring of G. For certain graphs G, a′(G) ≥ Δ(G) + 2 where Δ(G) is the maximum degree in G. It is known that a′(G) ≤ 16 Δ(G) for any graph G. We prove that there exists a constant c such that a′(G) ≤ Δ(G) + 2 for any graph G whose girth is at least cΔ(G) log Δ(G), and conjecture that this upper bound for a′(G) holds for all graphs G. We also show that a′(G) ≤ Δ + 2 for almost all Δ‐regular graphs. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 157–167, 2001     

Nonlinear dynamics of a ferrofluid pendulum

A ferrofluid torsion pendulum in an oscillating magnetic field exhibits a rich variety of nonlinear self-oscillatory regimes. The dynamics is governed by the system of coupled differential equations for the in- and off-axis components of the fluid magnetization and the pendulum angular deflection. In the limiting case of high driving frequency, the system reduces to the sole Rayleigh-type equation. Much more complicated temporal patterns arise when the field frequency and the pendulum eigen frequency are of the same order.     

On mappings of \mathbb{Q}^d to \mathbb{Q}^d that preserve distances 1 and \sqrt 2 and the Beckman-Quarles Theorem

Benz proved that every mapping that preserves the distances 1 and 2 is an isometry, provided d ≥ 5. We prove that every mapping that preserves the distances 1 and is an isometry, provided d ≥ 5.