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.

Finite domination and Novikov rings. Iterative approach

Suppose C is a bounded chain complex of finitely generated free modules over the Laurent polynomial ring L = R[x,x -1]. Then C is R-finitely dominated, i.e. homotopy equivalent over R to a bounded chain complex of finitely generated projective R-modules if and only if the two chain complexes C ? L R((x)) and C ? L R((x -1)) are acyclic, as has been proved by Ranicki (A. Ranicki, Finite domination and Novikov rings, Topology 34(3) (1995), 619–632). Here R((x)) = R[[x]][x -1] and R((x -1)) = R[[x -1]][x] are rings of the formal Laurent series, also known as Novikov rings. In this paper, we prove a generalisation of this criterion which allows us to detect finite domination of bounded below chain complexes of projective modules over Laurent rings in several indeterminates.

Discursive Control, Non-Domination and Hegelian Recognition Theory: Marrying Pettit’s Account(s) of Freedom with a Pippinian/Brandomian Reading of Hegelian Agency

The aim of this article is to combine Pettit’s account(s) of freedom, both his work on discursive control and on non-domination, with Pippin’s and Brandom’s reinterpretation of Hegelian rational agency and the role of recognition theory within it. The benefits of combining these two theories lie, as the article hopes to show, in three findings: first, re-examining Hegelian agency in the spirit of Brandom and Pippin in combination with Pettit’s views on freedom shows clearly why and in which way a Hegelian account of rational agency can ground an attractive socio-political account of freedom; second, the reconciling of discursive control and non-domination with Hegelian agency shows how the force and scope of recognition become finally tangible, without either falling into the trap of overburdening the concept, or merely reducing it to the idea of simple respect; third, the arguments from this article also highlight the importance of freedom as non-domination and how this notion is, indeed, as Pettit himself claims, an agency-freedom which aims at successfully securing the social, political, economic and even (some) psychological conditions for free and autonomous agency.

Finite domination and Novikov rings: Laurent polynomial rings in two variables

Let C be a bounded cochain complex of finitely generatedfree modules over the Laurent polynomial ring L = R[x, x−1, y, y−1].The complex C is called R-finitely dominated if it is homotopy equivalentover R to a bounded complex of finitely generated projective Rmodules.Our main result characterises R-finitely dominated complexesin terms of Novikov cohomology: C is R-finitely dominated if andonly if eight complexes derived from C are acyclic; these complexes areC ⊗L R[[x, y]][(xy)−1] and C ⊗L R[x, x−1][[y]][y−1], and their variants obtainedby swapping x and y, and replacing either indeterminate by its inverse.

Finite domination and Novikov rings. Laurent polynomial rings in several variables

We present a homological characterisation of those chain complexes of modules over a Laurent polynomial ring in several indeterminates which are finitely dominated over the ground ring (that is, are a retract up to homotopy of a bounded complex of finitely generated free modules). The main tools, which we develop in the paper, are a non-standard totalisation construction for multi-complexes based on truncated products, and a high-dimensional mapping torus construction employing a theory of cubical diagrams that commute up to specified coherent homotopies.

Exploring domination and subordination in high school physical education /

This is a critical qualitative inquiry into secondary school students' experiences of power relations within physical activity and physical education settings. More specifically the study examines the reproduction ofpower relations through the use of domination and subordination in physical activity and physical education. This study will attempt to understand power relations that take place between and among students and between teachers and students and how certain sports or activities reinforce power relationships within the gymnasium. Thirty eight first and second year university students completed a questionnaire which asked them to reflect upon their high school physical education experiences. Feedback fi*om the questionnaires described that highly skilled male students benefit the most fi-om high school physical education and receive more power and privilege when compared to lesser skilled students.

Estimates of Foraging Population and Territory of Heterotermes tenuis Colonies using Mark-Release-Recapture (Isoptera: Rhinotermitidae)

Heterotermes tenuis is an important economic pest in São Paulo state. Foraging populations of three field colonies of H. tenuis located on a University campus (UNESP, Rio Claro, SP, Brazil) were characterized. Foraging populations of H. tenuis colonies were calculated using four cycles of a mark-release-recapture program with a weighted mean method. The foraging population sizes of three colonies: A, B and C were 389,313±14,907; 265,589 ±12,635; and 641,600∓12,127; respectively. Foraging biomasses were 0.77 kg in the colony A, 0.51 kg in the colony B and 1.17 kg in colony C. Mean worker biomass was approximately 1.9 mg. Foraging territories occupied an area ranging from 70 m2 to 131 m2 per colony. The maximum linear foraging distance traveled by H. tenuis was 28m.

A manual of statutory corporation law : classified corporation laws of all the states, containing a digest of the business corporation laws of every state and territory of the United States, arranged uniformly, with the enactments of 1906 interleaved /

Includes bibliographical references and index.

How to be your own lawyer : a complete instructor for everybody ; adapted to every state and territory ; also a dictionary of legal terms /

Includes tables.

The United States blue book, a register of federal offices and employments in each state and territory and the District of Columbia, with their salaries and emoluments.

Mode of access: Internet.