Product Dimension of Forests and Bounded Treewidth Graphs

The product dimension of a graph G is defined as the minimum natural number l such that G is an induced subgraph of a direct product of l complete graphs. In this paper we study the product dimension of forests, bounded treewidth graphs and k-degenerate graphs. We show that every forest on n vertices has product dimension at most 1.441 log n + 3. This improves the best known upper bound of 3 log n for the same due to Poljak and Pultr. The technique used in arriving at the above bound is extended and combined with a well-known result on the existence of orthogonal Latin squares to show that every graph on n vertices with treewidth at most t has product dimension at most (t + 2) (log n + 1). We also show that every k-degenerate graph on n vertices has product dimension at most inverted right perpendicular5.545 k log ninverted left perpendicular + 1. This improves the upper bound of 32 k log n for the same by Eaton and Rodl.

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.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V(G) and edge set E(C). A k-dimensional box is a Cartesian product of closed intervals a(1), b(1)] x a(2), b(2)] x ... x a(k), b(k)]. The boxicity of G, box(G) is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes, i.e. each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset where S is the ground set and P is a reflexive, anti-symmetric and transitive binary relation on S. The dimension of P, dim(P) is the minimum integer l such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with its extended double cover, denoted as G(c). Let P-c be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P-c) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension. In the other direction, using the already known bounds for partial order dimension we get the following: (I) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta) which is an improvement over the best known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-epsilon)) for any epsilon > 0, unless NP=ZPP.

Boxicity and Poset Dimension

Let G be a simple, undirected, finite graph with vertex set V (G) and edge set E(G). A k-dimensional box is a Cartesian product of closed intervals [a(1), b(1)] x [a(2), b(2)] x ... x [a(k), b(k)]. The boxicity of G, box(G), is the minimum integer k such that G can be represented as the intersection graph of k-dimensional boxes; i.e., each vertex is mapped to a k-dimensional box and two vertices are adjacent in G if and only if their corresponding boxes intersect. Let P = (S, P) be a poset, where S is the ground set and P is a reflexive, antisymmetric and transitive binary relation on S. The dimension of P, dim(P), is the minimum integer t such that P can be expressed as the intersection of t total orders. Let G(P) be the underlying comparability graph of P; i.e., S is the vertex set and two vertices are adjacent if and only if they are comparable in P. It is a well-known fact that posets with the same underlying comparability graph have the same dimension. The first result of this paper links the dimension of a poset to the boxicity of its underlying comparability graph. In particular, we show that for any poset P, box(G(P))/(chi(G(P)) - 1) <= dim(P) <= 2box(G(P)), where chi(G(P)) is the chromatic number of G(P) and chi(G(P)) not equal 1. It immediately follows that if P is a height-2 poset, then box(G(P)) <= dim(P) <= 2box(G(P)) since the underlying comparability graph of a height-2 poset is a bipartite graph. The second result of the paper relates the boxicity of a graph G with a natural partial order associated with the extended double cover of G, denoted as G(c): Note that G(c) is a bipartite graph with partite sets A and B which are copies of V (G) such that, corresponding to every u is an element of V (G), there are two vertices u(A) is an element of A and u(B) is an element of B and {u(A), v(B)} is an edge in G(c) if and only if either u = v or u is adjacent to v in G. Let P(c) be the natural height-2 poset associated with G(c) by making A the set of minimal elements and B the set of maximal elements. We show that box(G)/2 <= dim(P(c)) <= 2box(G) + 4. These results have some immediate and significant consequences. The upper bound dim(P) <= 2box(G(P)) allows us to derive hitherto unknown upper bounds for poset dimension such as dim(P) = 2 tree width (G(P)) + 4, since boxicity of any graph is known to be at most its tree width + 2. In the other direction, using the already known bounds for partial order dimension we get the following: (1) The boxicity of any graph with maximum degree Delta is O(Delta log(2) Delta), which is an improvement over the best-known upper bound of Delta(2) + 2. (2) There exist graphs with boxicity Omega(Delta log Delta). This disproves a conjecture that the boxicity of a graph is O(Delta). (3) There exists no polynomial-time algorithm to approximate the boxicity of a bipartite graph on n vertices with a factor of O(n(0.5-is an element of)) for any is an element of > 0 unless NP = ZPP.

Dynamic Supply and Threshold Voltage Scaling for CMOS Digital Circuits Using In-Situ Power Monitor

A generalized power tracking algorithm that minimizes power consumption of digital circuits by dynamic control of supply voltage and the body bias is proposed. A direct power monitoring scheme is proposed that does not need any replica and hence can sense total power consumed by load circuit across process, voltage, and temperature corners. Design details and performance of power monitor and tracking algorithm are examined by a simulation framework developed using UMC 90-nm CMOS triple well process. The proposed algorithm with direct power monitor achieves a power savings of 42.2% for activity of 0.02 and 22.4% for activity of 0.04. Experimental results from test chip fabricated in AMS 350 nm process shows power savings of 46.3% and 65% for load circuit operating in super threshold and near sub-threshold region, respectively. Measured resolution of power monitor is around 0.25 mV and it has a power overhead of 2.2% of die power. Issues with loop convergence and design tradeoff for power monitor are also discussed in this paper.

Dynamic Supply and Threshold Voltage Scaling for CMOS Digital Circuits Using In-Situ Power Monitor

A generalized power tracking algorithm that minimizes power consumption of digital circuits by dynamic control of supply voltage and the body bias is proposed. A direct power monitoring scheme is proposed that does not need any replica and hence can sense total power consumed by load circuit across process, voltage, and temperature corners. Design details and performance of power monitor and tracking algorithm are examined by a simulation framework developed using UMC 90-nm CMOS triple well process. The proposed algorithm with direct power monitor achieves a power savings of 42.2% for activity of 0.02 and 22.4% for activity of 0.04. Experimental results from test chip fabricated in AMS 350 nm process shows power savings of 46.3% and 65% for load circuit operating in super threshold and near sub-threshold region, respectively. Measured resolution of power monitor is around 0.25 mV and it has a power overhead of 2.2% of die power. Issues with loop convergence and design tradeoff for power monitor are also discussed in this paper.

Urban water supply and management

Population growth and rapid urbanization lead to considerable stress on already depleting water resources. A great challenge for water authorities of urban cities is to supply adequate and reliable safe water to all consumers. In most of the developing countries water scarcity and high demands have led the water authorities to resort to intermittent supplies. Surface and groundwater are the major sources of supply in urban cities. The direct consequences of intermittent supplies and poor sanitation practices are several incidences of water borne diseases posing public health risk. In order to minimize the supply-demand gap and to assure good quality of water, new techniques or models can be helpful to manage the water distribution systems (WDS) in a better way. In the present paper, a review is carried out on the existing urban water supply management methodologies with a way forward for the proper management of the water supply systems.

How much land-based greenhouse gas mitigation can be achieved without compromising food security and environmental goals?

Feeding 9-10billion people by 2050 and preventing dangerous climate change are two of the greatest challenges facing humanity. Both challenges must be met while reducing the impact of land management on ecosystem services that deliver vital goods and services, and support human health and well-being. Few studies to date have considered the interactions between these challenges. In this study we briefly outline the challenges, review the supply- and demand-side climate mitigation potential available in the Agriculture, Forestry and Other Land Use AFOLU sector and options for delivering food security. We briefly outline some of the synergies and trade-offs afforded by mitigation practices, before presenting an assessment of the mitigation potential possible in the AFOLU sector under possible future scenarios in which demand-side measures codeliver to aid food security. We conclude that while supply-side mitigation measures, such as changes in land management, might either enhance or negatively impact food security, demand-side mitigation measures, such as reduced waste or demand for livestock products, should benefit both food security and greenhouse gas (GHG) mitigation. Demand-side measures offer a greater potential (1.5-15.6Gt CO2-eq. yr(-1)) in meeting both challenges than do supply-side measures (1.5-4.3Gt CO2-eq. yr(-1) at carbon prices between 20 and 100US$ tCO(2)-eq. yr(-1)), but given the enormity of challenges, all options need to be considered. Supply-side measures should be implemented immediately, focussing on those that allow the production of more agricultural product per unit of input. For demand-side measures, given the difficulties in their implementation and lag in their effectiveness, policy should be introduced quickly, and should aim to codeliver to other policy agenda, such as improving environmental quality or improving dietary health. These problems facing humanity in the 21st Century are extremely challenging, and policy that addresses multiple objectives is required now more than ever.

Decentralized demand-supply matching using community microgrids and consumer demand response: A scenario analysis

Developing countries constantly face the challenge of reliably matching electricity supply to increasing consumer demand. The traditional policy decisions of increasing supply and reducing demand centrally, by building new power plants and/or load shedding, have been insufficient. Locally installed microgrids along with consumer demand response can be suitable decentralized options to augment the centralized grid based systems and plug the demand-supply gap. The objectives of this paper are to: (1) develop a framework to identify the appropriate decentralized energy options for demand supply matching within a community, and, (2) determine which of these options can suitably plug the existing demand-supply gap at varying levels of grid unavailability. A scenario analysis framework is developed to identify and assess the impact of different decentralized energy options at a community level and demonstrated for a typical urban residential community Vijayanagar, Bangalore in India. A combination of LPG based CHP microgrid and proactive demand response by the community is the appropriate option that enables the Vijayanagar community to meet its energy needs 24/7 in a reliable, cost-effective manner. The paper concludes with an enumeration of the barriers and feasible strategies for the implementation of community microgrids in India based on stakeholder inputs. (C) 2014 Elsevier Ltd. All rights reserved.

Ferrous iron oxidation by foam immobilized Acidithiobacillus ferrooxidans: Experiments and modeling

Ferrous iron bio-oxidation by Acidithiobacillus ferrooxidans immobilized on polyurethane foam was investigated. Cells were immobilized on foams by placing them in a growth environment and fully bacterially activated polyurethane foams (BAPUFs) were prepared by serial subculturing in batches with partially bacterially activated foam (pBAPUFs). The dependence of foam density on cell immobilization process, the effect of pH and BAPUF loading on ferrous oxidation were studied to choose operating parameters for continuous operations. With an objective to have high cell densities both in foam and the liquid phase, pretreated foams of density 50 kg/m3 as cell support and ferrous oxidation at pH 1.5 to moderate the ferric precipitation were preferred. A novel basket-type bioreactor for continuous ferrous iron oxidation, which features a multiple effect of stirred tank in combination with recirculation, was designed and operated. The results were compared with that of a free cell and a sheet-type foam immobilized reactors. A fivefold increase in ferric iron productivity at 33.02 g/h/L of free volume in foam was achieved using basket-type bioreactor when compared to a free cell continuous system. A mathematical model for ferrous iron oxidation by Acidithiobacillus ferrooxidans cells immobilized on polyurethane foam was developed with cell growth in foam accounted by an effectiveness factor. The basic parameters of simulation were estimated using the experimental data on free cell growth as well as from cell attachment to foam under nongrowing conditions. The model predicted the phase of both oxidation of ferrous in shake flasks by pBAPUFs as well as by fully activated BAPUFs for different cell loadings in foam. Model for stirred tank basket bioreactor predicted within 5% both transient and steady state of the experiments closely for the simulated dilution rates. Bio-oxidation at high Fe2+ concentrations were simulated with experiments when substrate and product inhibition coefficients were factored into cell growth kinetics.

Design and development of a self-supported polymer electrolyte fuel cell system with anodic dead-end operation

Design and operational details for a self-supported polymer electrolyte fuel cell (PEFC) system with anodic dead-end fuel supply and internally humidified cathodic oxidant flow are described. During the PEFC operation, nitrogen and water back diffuse across the Nafion membrane from the cathode to the anode and accumulate in the anode flow channels affecting stack performance. The accumulated inert species are flushed from the stack by purging the fuel cell stack with a timer-activated purge valve to address the aforesaid problem. To minimize the system complexity, stack is designed in such a way that all the inert species accumulate in only one cell called the purge cell. A pulsed purge sequence comprises opening the valve for purge duration followed by purge-valve closing for the hold period and repeating the sequence in cycles. Since self-humidification is inadequate to keep the membrane wet, the anodic dead-end-operated PEFC stack with composite membrane comprising perflourosulphonic acid (Nafion) and silica is employed for keeping the membrane humidified even while operating the stack with dry hydrogen and internally humidified air.

Nonlinear dynamics of eucaryotic pyruvate dehydrogenase multienzyme complex: Decarboxylation rate, oscillations, and multiplicity

Pyruvate conversion to acetyl-CoA by the pyruvate dehydrogenase (PDH) multienzyme complex is known as a key node in affecting the metabolic fluxes of animal cell culture. However, its possible role in causing possible nonlinear dynamic behavior such as oscillations and multiplicity of animal cells has received little attention. In this work, the kinetic and dynamic behavior of PDH of eucaryotic cells has been analyzed by using both in vitro and simplified in vivo models. With the in vitro model the overall reaction rate (v(1)) of PDH is shown to be a nonlinear function of pyruvate concentration, leading to oscillations under certain conditions. All enzyme components affect v, and the nonlinearity of PDH significantly, the protein X and the core enzyme dihydrolipoamide acyltransferase (E2) being mostly predominant. By considering the synthesis rates of pyruvate and PDH components the in vitro model is expanded to emulate in vivo conditions. Analysis using the in vivo model reveals another interesting kinetic feature of the PDH system, namely, multiple steady states. Depending on the pyruvate and enzyme levels or the operation mode, either a steady state with high pyruvate decarboxylation rate or a steady state with significantly lower decarboxylation rate can be achieved under otherwise identical conditions. In general, the more efficient steady state is associated with a lower pyruvate concentration. A possible time delay in the substrate supply and enzyme synthesis can also affect the steady state to be achieved and lead's to oscillations under certain conditions. Overall, the predictions of multiplicity for the PDH system agree qualitatively well with recent experimental observations in animal cell cultures. The model analysis gives some hints for improving pyruavte metabolism in animal cell culture.

Groundwater Management in India:Physical, Institutional and Policy Alternatives

Groundwater constitutes a vital natural resource for sustaining India’s agricultural economy and meeting the country’s social, ecological and environmental goals. It is a unique resource, widely available, providing security against droughts and yet it is closely linked to surface-water resources and the hydrological cycle. Its availability depends on geo-hydrological conditions and characteristics of aquifers, from deep to alluvium, sediment crystalline rocks to basalt formations; and agro-climate from humid to subhumid and semi-arid to arid. Its reliable supply, uniform quality and temperature, relative turbidity, pollution-safe, minimal evaporation losses, and low cost of development are attributes making groundwater more attractive compared to other resources. It plays a key role in the provision of safe drinking water to rural populations. For example, already almost 80% of domestic water use in rural areas in India is groundwater-supplied, and much of it is being supplied to farms, villages and small towns. Inadequate control of the use of groundwater, indiscriminate application of agrochemicals and unrestrained pollution of the rural environment by other human activities make groundwater usage unsustainable, necessitating proper management in the face of the twin demand for water of good quality for domestic supply and adequate supply for irrigation, ensuring equity, efficiency and sustainability of the resource. Groundwater irrigation has overtaken surface irrigation in the early 1980s, supported by well energization. It is estimated that there are about 24 million energised wells and tube wells now and it is driven by demand rather than availability, evident through the greater occurrence of wells in districts with high population densities. Apart from aquifer characteristics, land fragmentation and landholding size are the factors that decide the density of wells. The ‘rise and fall’ of local economies dependent on groundwater can be summarized as: the green revolution of 1980s, groundwaterbased agrarian boom, early symptoms of groundwater overdraft, and decline of the groundwater socio-ecology. The social characteristics and policy interventions typical of each stage provide a fascinating insight into the human-resource dynamics. This book is a compilation of nine research papers discussing various aspects of groundwater management. It attempts to integrate knowledge about the physical system, the socio-economic system, the institutional set-up and the policy environment to come out with a more realistic analysis of the situation with regard to the nature, characteristics and intensity of resource use, the size of the economy the use generates, and the negative socioeconomic consequences. Complex variables addressed in this regard focusing on northern Gujarat are the stock of groundwater available in the region, its hydrodynamics, its net outflows against inflows, the economics of its intensive use (particularly irrigation in semi-arid and arid regions), its criticality in the regional hydroecological regime, ethical aspects and social aspects of its use. The first chapter by Dinesh Kumar and Singh, dwells on complex groundwater socio-ecology of India, while emphasizing the need for policy measures to address indiscriminate over-exploitation of dwindling resources. The chapter also explores the nature of groundwater economy and the role of electricity prices on it. The next chapter on groundwater issue in north Gujarat provides a description of groundwater resource characteristics followed by a detailed analysis of the groundwater depletion and quality deterioration problems in the region and their undesirable consequences on the economy, ecosystem health and the society. Considering water-buyers and wellowning farmers individually, a methodology for economic valuation of groundwater in regions where its primary usage is in agriculture, and as assessment of the groundwater economy based on case studies from north Gujarat is presented in the fourth chapter. The next chapter focuses on the extent of dependency of milk production on groundwater, which includes the water embedded in green and dry fodder and animal feed. The study made a realistic estimate of irrigation water productivity in terms of the physics and economics of milk production. The sixth chapter analyses the extent of reduction in water usage, increase in yield and overall increase in physical productivity of alfalfa with the use of the drip irrigation system. The chapter also provides a detailed synthesis of the costs and benefits associated with the use of drip irrigation systems. A linear programmingbased optimization model with the objective to minimize groundwater use taking into account the interaction between two distinct components – farming and dairying under the constraints of food security and income stability for different scenarios, including shift in cropping pattern, introduction of water-efficient crops, water- saving technologies in addition to the ‘business as usual’ scenario is presented in the seventh chapter. The results show that sustaining dairy production in the region with reduced groundwater draft requires crop shifts and adoption of water-saving technologies. The eighth chapter provides evidences to prove that the presence of adequate economic incentive would encourage farmers to adopt water-saving irrigation devices, based on the findings of market research with reference to the level of awareness among farmers of technologies and the factors that decide the adoption of water-saving technologies. However, now the marginal cost of using electricity for agricultural pumping is almost zero. The economic incentives are strong and visible only when the farmers are either water-buyers or have to manage irrigation with limited water from tube-well partnerships. The ninth chapter explores the socio-economic viability of increasing the power tariff and inducing groundwater rationing as a tool for managing energy and groundwater demand, considering the current estimate of the country’s annual economic loss of Rs 320 billion towards electricity subsidy in the farm sector. The tenth chapter suggests private tradable property rights and development of water markets as the institutional tool for achieving equity, efficiency and sustainability of groundwater use. It identifies the externalities for local groundwater management and emphasizes the need for managing groundwater by local user groups, supported by a thorough analysis of groundwater socio-ecology in India. An institutional framework for managing the resource based on participatory approach that is capable of internalizing the externalities, comprising implementation of institutional and technical alternatives for resource management is also presented. Major findings of the analyses and key arguments in each chapter are summarized in the concluding chapter. Case studies of the social and economic benefits of groundwater use, where that use could be described as unsustainable, are interesting. The benefits of groundwater use are outlined and described with examples of social and economic impacts of groundwater and the negative aspects of groundwater development with the compilation of environmental problems based on up-to-date research results. This publication with a well-edited compilation of case studies is informative and constitutes a useful publication for students and professionals.

Projecting low and extensive dimensional chaos from spatio-temporal dynamics

We review the spatio-temporal dynamical features of the Ananthakrishna model for the Portevin-Le Chatelier effect, a kind of plastic instability observed under constant strain rate deformation conditions. We then establish a qualitative correspondence between the spatio-temporal structures that evolve continuously in the instability domain and the nature of the irregularity of the scalar stress signal. Rest of the study is on quantifying the dynamical information contained in the stress signals about the spatio-temporal dynamics of the model. We show that at low applied strain rates, there is a one-to-one correspondence with the randomly nucleated isolated bursts of mobile dislocation density and the stress drops. We then show that the model equations are spatio-temporally chaotic by demonstrating the number of positive Lyapunov exponents and Lyapunov dimension scale with the system size at low and high strain rates. Using a modified algorithm for calculating correlation dimension density, we show that the stress-strain signals at low applied strain rates corresponding to spatially uncorrelated dislocation bands exhibit features of low dimensional chaos. This is made quantitative by demonstrating that the model equations can be approximately reduced to space independent model equations for the average dislocation densities, which is known to be low-dimensionally chaotic. However, the scaling regime for the correlation dimension shrinks with increasing applied strain rate due to increasing propensity for propagation of the dislocation bands. The stress signals in the partially propagating to fully propagating bands turn to have features of extensive chaos.

Query Click and Text Similarity Graph for Query Suggestions

Query suggestion is an important feature of the search engine with the explosive and diverse growth of web contents. Different kind of suggestions like query, image, movies, music and book etc. are used every day. Various types of data sources are used for the suggestions. If we model the data into various kinds of graphs then we can build a general method for any suggestions. In this paper, we have proposed a general method for query suggestion by combining two graphs: (1) query click graph which captures the relationship between queries frequently clicked on common URLs and (2) query text similarity graph which finds the similarity between two queries using Jaccard similarity. The proposed method provides literally as well as semantically relevant queries for users' need. Simulation results show that the proposed algorithm outperforms heat diffusion method by providing more number of relevant queries. It can be used for recommendation tasks like query, image, and product suggestion.