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.

Open-circuit potential—time transients of alkaline porous iron electrodes at various states-of-charge

Open-circuit potential—time transients during the discharge of alkaline porous iron electrodes at various states-of-charge have been studied. From this, it has been possible to arrive at a correlation between the parameters of self-discharge kinetics of the electrode and observed open-circuit potential—recovery time constants. The study provides a method of estimate the state-of-charge of the rechargeable iron electrodes. As a hydrogen evolution reaction inevitably occurs on alkaline iron electrodes, the kinetics of the reaction have also been investigated.

Estimation Of Charge Transport Parameters And Equivalent Circuit For Poly Alkyl Thiophene Field-Effect Transistors

The small signal ac response is measured across the source-drain terminals of organic field-effect transistors (OFET) under dc bias to obtain the equivalent circuit parameters of poly(2,5-bis(3-tetradecylthiophen-2-yl)thieno[3,2-b]thiophene) (PBTTT) and poly(3-hexyl thiophene) (P3HT) based devices. The numerically simulated response based on these parameters is in good agreement with the experimental data for PBTTT-FET except at low frequencies, while the P3HT-FET data show significant deviations. This indicates that the interface with the metal electrode is rather complex for the latter, involving additional circuit elements arising from contact impedance or charge injection processes. Such an investigation can help in identifying the operational bottlenecks and to improve the performance of OFETs.

Circuit layout through an analogy with neural networks

Standard-cell design methodology is an important technique in semicustom-VLSI design. It lends itself to the easy automation of the crucial layout part, and many algorithms have been proposed in recent literature for the efficient placement of standard cells. While many studies have identified the Kerninghan-Lin bipartitioning method as being superior to most others, it must be admitted that the behaviour of the method is erratic, and that it is strongly dependent on the initial partition. This paper proposes a novel algorithm for overcoming some of the deficiencies of the Kernighan-Lin method. The approach is based on an analogy of the placement problem with neural networks, and, by the use of some of the organizing principles of these nets, an attempt is made to improve the behavior of the bipartitioning scheme. The results have been encouraging, and the approach seems to be promising for other NP-complete problems in circuit layout.

A Circuit-Based Proof of Toda′s Theorem

We present a simple proof of Toda′s result (Toda (1989), in "Proceedings, 30th Annual IEEE Symposium on Foundations of Computer Science," pp. 514-519), which states that circled plus P is hard for the Polynomial Hierarchy under randomized reductions. Our approach is circuit-based in the sense that we start with uniform circuit definitions of the Polynomial Hierarchy and apply the Valiant-Vazirani lemma on these circuits (Valiant and Vazirani (1986), Thoeret. Comput. Sci.47, 85-93).

A simple equivalent circuit analysis of rectangular folded-waveguide slow-wave structure

A simple yet accurate equivalent circuit model was developed for the analysis of slow-wave properties (dispersion and interaction impedance characteristics) of a rectangular folded-waveguide slow-wave structure. Present formulation includes the effects of the presence of beam-hole in the circuit, which were ignored in existing approaches. The analysis was benchmarked against measurement as well as with 3D electromagnetic modeling using MAFIA for two typical slow-wave structures operating in Ka- and Q-bands, and close agreements were observed. The analysis was extended for demonstrating the effect of the variation of beam-hole radius on the RF interaction efficiency of the device. (C) 2009 Elsevier GmbH. All rights reserved.

Hierarchies of circuit classes that are closed under complement

We examine three hierarchies of circuit classes and show they are closed under complementation. (1) The class of languages recognized by a family of polynomial size skew circuits with width O(w), are closed under complement. (2) The class of languages recognized by family of polynomial size circuits with width O(w) and polynomial tree-size, are closed under complement. (3) The class of languages recognized by a family of polynomial size, O(log(n)) depth, bounded AND fan-in with OR fan-in f (f⩾log(n)) circuits are closed under complement. These improve upon the results of (i) Immerman (1988) and Szelepcsenyi (1988), who show that 𝒩L𝒪𝒢 is closed under complementation, and (ii) Borodin et al. (1989), who show that L𝒪𝒢𝒞ℱL is closed under complement

Hybrid LCI/VSI Power Circuit-A Universal High-Power Converter Solution for Wound Field Synchronous Motor Drives

Load commutated inverter (LCI)-fed wound field synchronous motor drives are used for medium-voltage high-power drive applications. This drive suffers from drawbacks such as complex starting procedure, sixth harmonic torque pulsations, quasi square wave motor current, notches in the terminal voltages, etc. In this paper, a hybrid converter circuit, consisting of an LCI and a voltage source inverter (VSI), is proposed, which can be a universal high-power converter solution for wound field synchronous motor drives. The proposed circuit, with the addition of a current-controlled VSI, overcomes nearly all of the shortcomings present in the conventional LCI-based system besides providing many additional advantages. In the proposed drive, the motor voltage and current are always sinusoidal even with the LCI switching at the fundamental frequency. The performance of the drive is demonstrated with detailed experimental waveforms from a 15.8-hp salient pole wound field synchronous machine. Finally, a brief description of the control scheme used for the proposed circuit is given.

An Investigation into the Dependence of the Arc Voltage on the Parameters of the Short-Circuit Current and the Design of the Vacuum Interrupter

The vacuum interrupter is extensively employed in the medium voltage switchgear for the interruption of the short-circuit current. The voltage across the arc during current interruption is termed as the arc voltage. The nature and magnitude of this arc voltage is indicative of the performance of the contacts and the vacuum interrupter as a whole. Also, the arc voltage depends on the parameters like the magnitude of short-circuit current, the arcing time, the point of opening of the contacts, the geometry and area of the contacts and the type of magnetic field. This paper investigates the dependency of the arc voltage on some of these parameters. The paper also discusses the usefulness of the arc voltage in diagnosing the performance of the contacts.

Bounds on Defect Level and Fault Coverage in Linear Analog Circuit Testing

Transfer function coefficients (TFC) are widely used to test linear analog circuits for parametric and catastrophic faults. This paper presents closed form expressions for an upper bound on the defect level (DL) and a lower bound on fault coverage (FC) achievable in TFC based test method. The computed bounds have been tested and validated on several benchmark circuits. Further, application of these bounds to scalable RC ladder networks reveal a number of interesting characteristics. The approach adopted here is general and can be extended to find bounds of DL and FC of other parametric test methods for linear and non-linear circuits.

Modeling of the Effects of Process Variations on Circuit Delay at 65nm

A novel methodology for modeling the effects of process variations on circuit delay performance is proposed by relating the variations in process parameters to variations in delay metric of a complex digital circuit. The delay of a 2-input NAND gate with 65nm gate length transistors is extensively characterized by mixed-mode simulations which is then used as a library element. The variation in saturation current Ionat the device level, and the variation in rising/falling edge stage delay for the NAND gate at the circuit level, are taken as performance metrics. A 4-bit x 4-bit Wallace tree multiplier circuit is used as a representative combinational circuit to demonstrate the proposed methodology. The variation in the multiplier delay is characterized, to obtain delay distributions, by an extensive Monte Carlo analysis. An analytical model based on CV/I metric is proposed, to extend this methodology for a generic technology library with a variety of library elements.

Towards formal verification of analog mixed signal designs using SPICE circuit simulation traces

An extension to a formal verification approach of hybrid systems is proposed to verify analog and mixed signal (AMS) designs. AMS designs can be formally modeled as hybrid systems and therefore lend themselves to the formal analysis and verification techniques applied to hybrid systems. The proposed approach employs simulation traces obtained from an actual design implementation of AMS circuit blocks (for example, in the form of SPICE netlists) to carry out formal analysis and verification. This enables the same platform used for formally validating an abstract model of an AMS design, to be also used for validating its different refinements and design implementation; thereby, providing a simple route to formal verification at different levels of implementation. The feasibility of the proposed approach is demonstrated with a case study based on a tunnel diode oscillator. Since the device characteristic of a tunnel diode is highly non-linear with a negative resistance region, dynamic behavior of circuits in which it is employed as an element is difficult to model, analyze and verify within a general hybrid system formal verification tool. In the case study presented the formal model and the proposed computational techniques have been incorporated into CheckMate, a formal verification tool based on MATLAB and Simulink-Stateflow Framework from MathWorks.

Formulas for algorithmic computation of impedance matrix using general circuit constants

A set of formulas is derived from general circuit constants which facilitates formation of the impedance matrix of a power system by the bus-impedance method. The errors associated with the lumpedparameter representation of a transmission line are thereby eliminated. The formulas are valid for short lines also, if the relevant general circuit constants are employed. The mutual impedance between the added line and the existing system is not considered, but the approach suggested can well be extended to it.