The hardness of approximating the boxicity, cubicity and threshold dimension of a graph

A k-dimensional box is the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the Cartesian product R-1 X R-2 X ... X R-k where each R-i is a closed interval oil the real line of the form a(i), a(i) + 1]. The cubicity of G, denoted as cub(G), is the minimum integer k such that G can be represented as the intersection graph of a collection of k-cubes. The threshold dimension of a graph G(V, E) is the smallest integer k such that E can be covered by k threshold spanning subgraphs of G. In this paper we will show that there exists no polynomial-time algorithm for approximating the threshold dimension of a graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. From this result we will show that there exists no polynomial-time algorithm for approximating the boxicity and the cubicity of a graph on n vertices with factor O(n(0.5-epsilon)) for any epsilon > 0 unless NP = ZPP. In fact all these hardness results hold even for a highly structured class of graphs, namely the split graphs. We will also show that it is NP-complete to determine whether a given split graph has boxicity at most 3. (C) 2010 Elsevier B.V. All rights reserved.

Eigenvalues of kinematical conservation laws (KCL) based 3-D weakly nonlinear ray theory (WNLRT)

System of kinematical conservation laws (KCL) govern evolution of a curve in a plane or a surface in space, even if the curve or the surface has singularities on it. In our recent publication K. R. Arun, P. Prasad, 3-D kinematical conservation laws (KCL): evolution of a surface in R-3-in particular propagation of a nonlinear wavefront, Wave Motion 46 (2009) 293-311] we have developed a mathematical theory to study the successive positions and geometry of a 3-D weakly nonlinear wavefront by adding an energy transport equation to KCL. The 7 x 7 system of equations of this KCL based 3-D weakly nonlinear ray theory (WNLRT) is quite complex and explicit expressions for its two nonzero eigenvalues could not be obtained before. In this short note, we use two different methods: (i) the equivalence of KCL and ray equations and (ii) the transformation of surface coordinates, to derive the same exact expressions for these eigenvalues. The explicit expressions for nonzero eigenvalues are important also for checking stability of any numerical scheme to solve 3-D WNLRT. (C) 2010 Elsevier Inc. All rights reserved.

Invariant norm quantifying nonlinear content of Hamiltonian systems

Given a Hamiltonian system, one can represent it using a symplectic map. This symplectic map is specified by a set of homogeneous polynomials which are uniquely determined by the Hamiltonian. In this paper, we construct an invariant norm in the space of homogeneous polynomials of a given degree. This norm is a function of parameters characterizing the original Hamiltonian system. Such a norm has several potential applications. (C) 2010 Elsevier Inc. All rights reserved.

Flow And Heat-Transfer Over An Upstream Moving Wall With A Magnetic-Field And A Parallel Free Stream

The flow and heat transfer over an upstream moving non-isothermal wall with a parallel free stream have been considered. The magnetic field has been applied in the free stream parallel to the wall and the effect of induced magnetic field has been included in the analysis. The boundary layer equations governing the steady incompressible electrically conducting fluid flow have been solved numerically using a shooting method. This problem is interesting because a solution exists only when the ratio of the wall velocity does not exceed a certain critical value and this critical value depends on the magnetic field and magnetic Prandtl number. Also dual solutions exist for a certain range of wall velocity.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

Solution of a Boundary-Value Problem associated with Diffraction of Water Waves by a Nearly Vertical Barrier

An exact solution is derived for a boundary-value problem for Laplace's equation which is a generalization of the one occurring in the course of solution of the problem of diffraction of surface water waves by a nearly vertical submerged barrier. The method of solution involves the use of complex function theory, the Schwarz reflection principle, and reduction to a system of two uncoupled Riemann-Hilbert problems. Known results, representing the reflection and transmission coefficients of the water wave problem involving a nearly vertical barrier, are derived in terms of the shape function.

A Direct Approach to the Problem of Diffraction by a Half-Plane under Mixed Boundary Conditions

A general direct technique of solving a mixed boundary value problem in the theory of diffraction by a semi-infinite plane is presented. Taking account of the correct edge-conditions, the unique solution of the problem is derived, by means of Jones' method in the theory of Wiener-Hopf technique, in the case of incident plane wave. The solution of the half-plane problem is found out in exact form. (The far-field is derived by the method of steepest descent.) It is observed that it is not the Wiener-Hopf technique which really needs any modification but a new technique is certainly required to handle the peculiar type of coupled integral equations which the Wiener-Hopf technique leads to. Eine allgemeine direkte Technik zur Lösung eines gemischten Randwertproblems in der Theorie der Beugung an einer halbunendlichen Ebene wird vorgestellt. Unter Berücksichtigung der korrekten Eckbedingungen wird mit der Methode von Jones aus der Theorie der Wiener-Hopf-Technik die eindeutige Lösung für den Fall der einfallenden ebenen Welle hergeleitet. Die Lösung des Halbebenenproblems wird in exakter Form angegeben. (Das Fernfeld wurde mit der Methode des steilsten Abstiegs bestimmt.) Es wurde bemerkt, daß es nicht die Wiener-Hopf-Technik ist, die wirklich irgend welcher Modifikationen bedurfte. Gewiß aber wird eine neue Technik zur Behandlung des besonderen Typs gekoppelter Integralgleichungen benötigt, auf die die Wiener-Hopf-Technik führt.

A New Approach to the Problem of Scattering of Water Waves by Vertical Barriers

Using a modified Green's function technique the two well-known basic problems of scattering of surface water waves by vertical barriers are reduced to the problem of solving a pair of uncoupled integral equations involving the “jump” and “sum” of the limiting values of the velocity potential on the two sides of the barriers in each case. These integral equations are then solved, in closed form, by the aid of an integral transform technique involving a general trigonometric kernel as applicable to the problems associated with a radiation condition.

Exact traveling- wave solution for model geophysical systems

Exact traveling-wave solutions of time-dependent nonlinear inhomogeneous PDEs, describing several model systems in geophysical fluid dynamics, are found. The reduced nonlinear ODEs are treated as systems of linear algebraic equations in the derivatives. A variety of solutions are found, depending on the rank of the algebraic systems. The geophysical systems include acoustic gravity waves, inertial waves, and Rossby waves. The solutions describe waves which are, in general, either periodic or monoclinic. The present approach is compared with the earlier one due to Grundland (1974) for finding exact solutions of inhomogeneous systems of nonlinear PDEs.