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.

The Blackett Memorial Lecture, 1991: Chemical Insights into High-Temperature Superconductors

The high-temperature superconductors are complex oxides, generally containing two-dimensional CuO2 sheets. Various families of the cuprate superconductors are described, paying special attention to aspects related to oxygen stoichiometry, phase stability, synthesis and chemical manipulation of charge carriers. Other aspects discussed are chemical applications of cuprates, possibly as gas sensors and copper-free oxide superconductors. All but the substituted Nd and Pr cuprates are hole-superconductors. Several families of cuprates show a nearly constant n(h) at maximum T(c). Besides this universality, the cuprates exhibit a number of striking common features. Based on Cu(2p) photoemission studies, it is found that the Cu-O charge-transfer energy, DELTA, and the Cu(3d)-O(2p) hybridization strength, t(pd), are key factors in the superconductivity of cuprates. The relative intensity of the satellite in the Cu(2p) core-level spectra, the polarizability of the CuO2 sheets as well as the hole concentration are related to DELTA/t(pd). These chemical bonding factors have to be explicitly taken into account in any model for superconductivity of the cuprates.

A Multi frequency study of Radio Intensity Variations For Active Galactic Nuclei of Different Optical Classes

A study of radio intensity variations at seven frequencies in the range 0.3 to 90 GHz for compact extragalactic radio sources classified as BL Lacs and high- and low-optical polarization quasars (HPQs and LPQs) is presented. This include the results of flux-density monitoring of 33 compact sources for three years at 327 MHz with the Ooty Synthesis Radio Telescope. The degrees of 'short-term' (tau less than about 1 yr) variability for the three optical types are found to be indistinguishable at low frequencies (less than 1 GHz), pointing to an extrinsic origin for the low-frequency variability. At high frequencies, a distinct dependence on optical type is present, the variability increasing from LPQs, through HPQs to BL Lacs. This trend persists even when only sources with ultra-flat radio spectra (alpha greater than -0.2) are considered. Implications of this for the phenomenon of high-frequency variability and the proposed unification schemes for different optical types of active galactic nuclei are discussed.

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

A fault-tolerant distributed deadlock detection algorithm

In this paper, we propose a new fault-tolerant distributed deadlock detection algorithm which can handle loss of any resource release message. It is based on a token-based distributed mutual exclusion algorithm. We have evaluated and compared the performance of the proposed algorithm with two other algorithms which belong to two different classes, using simulation studies. The proposed algorithm is found to be efficient in terms of average number of messages per wait and average deadlock duration compared to the other two algorithms in all situations, and has comparable or better performance in terms of other parameters.

Optimal feature extraction for bilingual OCR

Feature extraction in bilingual OCR is handicapped by the increase in the number of classes or characters to be handled. This is evident in the case of Indian languages whose alphabet set is large. It is expected that the complexity of the feature extraction process increases with the number of classes. Though the determination of the best set of features that could be used cannot be ascertained through any quantitative measures, the characteristics of the scripts can help decide on the feature extraction procedure. This paper describes a hierarchical feature extraction scheme for recognition of printed bilingual (Tamil and Roman) text. The scheme divides the combined alphabet set of both the scripts into subsets by the extraction of certain spatial and structural features. Three features viz geometric moments, DCT based features and Wavelet transform based features are extracted from the grouped symbols and a linear transformation is performed on them for the purpose of efficient representation in the feature space. The transformation is obtained by the maximization of certain criterion functions. Three techniques : Principal component analysis, maximization of Fisher's ratio and maximization of divergence measure have been employed to estimate the transformation matrix. It has been observed that the proposed hierarchical scheme allows for easier handling of the alphabets and there is an appreciable rise in the recognition accuracy as a result of the transformations.

Local Structural Differences in Homologous Proteins: Specificities in Different SCOP Classes

The constant increase in the number of solved protein structures is of great help in understanding the basic principles behind protein folding and evolution. 3-D structural knowledge is valuable in designing and developing methods for comparison, modelling and prediction of protein structures. These approaches for structure analysis can be directly implicated in studying protein function and for drug design. The backbone of a protein structure favours certain local conformations which include alpha-helices, beta-strands and turns. Libraries of limited number of local conformations (Structural Alphabets) were developed in the past to obtain a useful categorization of backbone conformation. Protein Block (PB) is one such Structural Alphabet that gave a reasonable structure approximation of 0.42 angstrom. In this study, we use PB description of local structures to analyse conformations that are preferred sites for structural variations and insertions, among group of related folds. This knowledge can be utilized in improving tools for structure comparison that work by analysing local structure similarities. Conformational differences between homologous proteins are known to occur often in the regions comprising turns and loops. Interestingly, these differences are found to have specific preferences depending upon the structural classes of proteins. Such class-specific preferences are mainly seen in the all-beta class with changes involving short helical conformations and hairpin turns. A test carried out on a benchmark dataset also indicates that the use of knowledge on the class specific variations can improve the performance of a PB based structure comparison approach. The preference for the indel sites also seem to be confined to a few backbone conformations involving beta-turns and helix C-caps. These are mainly associated with short loops joining the regular secondary structures that mediate a reversal in the chain direction. Rare beta-turns of type I' and II' are also identified as preferred sites for insertions.

Open Media Classes at Coventry University: Final Evaluation Report 2015

This report offers a reflection on findings from a one year evaluation study into the distributed open media classes at Coventry University The study team comprised Lou McGill and Tim Gray of Lou McGill Consultancy Ltd. This report is augmented by an open wiki (bit.ly/1KqL4nH) which includes more detail about the approaches used during the study and findings are also presented as a series of web pages (comc.loumcgill.co.uk). We would like to thank the Department of Media in the School of Art and Design for their input, openness and patience during the study.

Histoire de Portugal : contenant les enterprises, navigations, & gestes memorables des Portugallois, tant en la cõqueste des Indes Orientales par eux descouvertes, qu'és guerres d'Afrique & autres exploits, depuis l'an mil quatre cens nonãte six, jusques à l'an mil cinq cens septante huit, sous Emmanuel premier, Jean troisieme, & Sebastian premier du nom / Pour Antoine Chuppin, ed. ; comprinse en vingt livres, dont les douze premiers sont traduits du latin de Ierosme Osorius, Euesque de Sylues en Algarve, les huit suivans prins de Lopez de Castagnede & d'autres historiensNouvellement mise en françois, par S.G.S. avec un discours du fruit qu'on peut recueillir de la lecture de cette histoire, & ample indice des matieres principales y contenues

Contém os empreendimentos, as navegações e os gestos memoráveis dos portugueses, inclusive em suas colônias.