Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

A Non Quasi-Static Small Signal Model for Long Channel Symmetric DG MOSFET

We propose a compact model for small signal non quasi static analysis of long channel symmetric double gate MOSFET The model is based on the EKV formalism and is valid in all regions of operation and thus suitable for RF circuit design Proposed model is verified with professional numerical device simulator and excellent agreement is found well beyond the cut-off frequency

Error-free matrix symmetrizers and equivalent symmetric matrices

A symmetrizer of the matrix A is a symmetric solution X that satisfies the matrix equation XA=AprimeX. An exact matrix symmetrizer is computed by obtaining a general algorithm and superimposing a modified multiple modulus residue arithmetic on this algorithm. A procedure based on computing a symmetrizer to obtain a symmetric matrix, called here an equivalent symmetric matrix, whose eigenvalues are the same as those of a given real nonsymmetric matrix is presented.

Analogues of the Wiener-Tauberian and Schwartz theorems for radial functions on symmetric spaces

We prove a Wiener Tauberian theorem for the L-1 spherical functions on a semisimple Lie group of arbitrary real rank. We also establish a Schwartz-type theorem for complex groups. As a corollary we obtain a Wiener Tauberian type result for compactly supported distributions.

Stabilizing trench's algorithm to invert symmetric toeplitz matrices

Presented here is a stable algorithm that uses Zohar's formulation of Trench's algorithm and computes the inverse of a symmetric Toeplitz matrix including those with vanishing or nearvanishing leading minors. The algorithm is based on a diagonal modification of the matrix, and exploits symmetry and persymmetry properties of the inverse matrix.

Coherence of the real symmetric Hardy algebra

Let D denote the open unit disk in C centered at 0. Let H-R(infinity) denote the set of all bounded and holomorphic functions defined in D that also satisfy f(z) = <(f <(z)over bar>)over bar> for all z is an element of D. It is shown that H-R(infinity) is a coherent ring.

Escape of high mass ions due to initial thermal energy and its implications for axially symmetric RF ion trap mass analyzer design

This paper investigates the loss of high mass ions due to their initial thermal energy in ion trap mass analyzers. It provides an analytical expression for estimating the percentage loss of ions of a given mass at a particular temperature, in a trap operating under a predetermined set of conditions. The expression we developed can be used to study the loss of ions due to its initial thermal energy in traps which have nonlinear fields as well as those which have linear fields. The expression for the percentage of ions lost is shown to be a function of the temperature of the ensemble of ions, ion mass and ion escape velocity. An analytical expression for the escape velocity has also been derived in terms of the trapping field, drive frequency and ion mass. Because the trapping field is determined by trap design parameters and operating conditions, it has been possible to study the influence of these parameters on ion loss. The parameters investigated include ion temperature, magnitude of the initial potential applied to the ring electrode (which determines the low mass cut-off), trap size, dimensions of apertures in the endcap electrodes and RF drive frequency. Our studies demonstrate that ion loss due to initial thermal energy increases with increase in mass and that, in the traps investigated, ion escape occurs in the radial direction. Reduction in the loss of high mass ions is favoured by lower ion temperatures, increasing low mass cut-off, increasing trap size, and higher RF drive frequencies. However, dimensions of the apertures in the endcap electrodes do not influence ion loss in the range of aperture sizes considered. (C) 2010 Elsevier B.V. All rights reserved.

Multigrid algorithms for symmetric discontinuous Galerkin methods on graded meshes

We study a class of symmetric discontinuous Galerkin methods on graded meshes. Optimal order error estimates are derived in both the energy norm and the L 2 norm, and we establish the uniform convergence of V-cycle, F-cycle and W-cycle multigrid algorithms for the resulting discrete problems. Numerical results that confirm the theoretical results are also presented.

Improved ferroelectric and leakage properties in symmetric BiFeO3/SrTiO3 superlattice

Symmetric BiFeO3/SrTiO3 superlattices were fabricated by pulsed laser deposition on SrTiO3 (100) substrates. Frequency independent and near saturated P-E hysteresis was observed in the case of a superlattice (periodicity of ∼ 11 nm) as compared to leaky hysteresis observed in epitaxial BiFeO3. Room temperature leakage current density of the superlattice was almost two orders of magnitude lower than that of BiFeO3. Observed leakage current behavior in case of both BiFeO3 and superlattice indicates the dominance of space charge limited conduction. Improvement in ferroelectric property was discussed in connection to enhanced epitaxial strain, reduced leakage current, and electrostatic interaction between BiFeO3 and SrTiO3.

A Simple Charge Model for Symmetric Double-Gate MOSFETs Adapted to Gate-Oxide-Thickness Asymmetry

Surface-potential-based compact charge models for symmetric double-gate metal-oxide-semiconductor field-effect transistors (SDG-MOSFETs) are based on the fundamental assumption of having equal oxide thicknesses for both gates. However, for practical devices, there will always be some amount of asymmetry between the gate oxide thicknesses due to process variations and uncertainties, which can affect device performance significantly. In this paper, we propose a simple surface-potential-based charge model, which is applicable for tied double-gate MOSFETs having same gate work function but could have any difference in gate oxide thickness. The proposed model utilizes the unique so-far-unexplored quasi-linear relationship between the surface potentials along the channel. In this model, the terminal charges could be computed by basic arithmetic operations from the surface potentials and applied biases, and thus, it could be implemented in any circuit simulator very easily and extendable to short-channel devices. We also propose a simple physics-based perturbation technique by which the surface potentials of an asymmetric device could be obtained just by solving the input voltage equation of SDG devices for small asymmetry cases. The proposed model, which shows excellent agreement with numerical and TCAD simulations, is implemented in a professional circuit simulator through the Verilog-A interface and demonstrated for a 101-stage ring oscillator simulation. It is also shown that the proposed model preserves the source/drain symmetry, which is essential for RF circuit design.