Approximation algorithm for maximum independent set in planar traingle-free graphs

The maximum independent set problem is NP-complete even when restricted to planar graphs, cubic planar graphs or triangle free graphs. The problem of finding an absolute approximation still remains NP-complete. Various polynomial time approximation algorithms, that guarantee a fixed worst case ratio between the independent set size obtained to the maximum independent set size, in planar graphs have been proposed. We present in this paper a simple and efficient, O(|V|) algorithm that guarantees a ratio 1/2, for planar triangle free graphs. The algorithm differs completely from other approaches, in that, it collects groups of independent vertices at a time. Certain bounds we obtain in this paper relate to some interesting questions in the theory of extremal graphs.

Ant colony optimization for reporting cell planning in mobile computing using selective paging strategy

Location management problem that arise in mobile computing networks is addressed. One method used in location management is to designate sonic of the cells in the network as "reporting cells". The other cells in the network are "non-reporting cells". Finding an optimal set of reporting cells (or reporting cell configuration) for a given network. is a difficult combinatorial optimization problem. In fact this is shown to be an NP-complete problem. in an earlier study. In this paper, we use the selective paging strategy and use an ant colony optimization method to obtain the best/optimal set of reporting cells for a given a network.

Artificial neural networks and multicriterion analysis for sustainable irrigation planning

The objective of the present paper is to select the best compromise irrigation planning strategy for the case study of Jayakwadi irrigation project, Maharashtra, India. Four-phase methodology is employed. In phase 1, separate linear programming (LP) models are formulated for the three objectives, namely. net economic benefits, agricultural production and labour employment. In phase 2, nondominated (compromise) irrigation planning strategies are generated using the constraint method of multiobjective optimisation. In phase 3, Kohonen neural networks (KNN) based classification algorithm is employed to sort nondominated irrigation planning strategies into smaller groups. In phase 4, multicriterion analysis (MCA) technique, namely, Compromise Programming is applied to rank strategies obtained from phase 3. It is concluded that the above integrated methodology is effective for modeling multiobjective irrigation planning problems and the present approach can be extended to situations where number of irrigation planning strategies are even large in number. (c) 2004 Elsevier Ltd. All rights reserved.

Assessing the critical concentration of NH2 terminal groups on the surface of MWNTs towards chain scission of PC in PC/SAN blends: effect on dispersion, electrical conductivity and EMI shielding

The localization and dispersion quality of as received NH2 terminated multiwall carbon nanotubes (MWNT-I) and ethylene diamine (EDA) functionalized MWNTs in melt mixed blends of polycarbonate ( PC) and poly(styrene-co-acrylonitrile) (SAN) were assessed in this study using rheo-electrical and electromagnetic interference (EMI) shielding measurements. In order to improve the dispersion quality and also to selectively localize MWNTs in the PC phase of the blends, EDA was grafted onto MWNTs by two different strategies like diazonium reaction of the para-substituted benzene ring of MWNTs with EDA ( referred to as MWNT-II) and acylation of carboxyl functionalized MWNTs with thionyl chloride ( referred to as MWNT-III). By this approach we could systematically vary the concentration of NH2 functional groups on the surface of MWNTs at a fixed concentration (1 wt%) in PC/SAN blends. XPS was carried to evaluate the % concentration of N in different MWNTs and was observed to be highest for MWNT-III manifesting in a large surface coverage of EDA on the surface of MWNTs. Viscoelastic properties and melt electrical conductivities were measured to assess the dispersion quality of MWNTs using a rheo-electrical set-up both in the quiescent as well as under steady shear conditions. Rheological properties revealed chain scission of PC in the presence of MWNT-III which is due to specific interactions between EDA and PC leading to smaller PC grafts on the surface of MWNTs. The observed viscoelastic properties in the blends were further correlated with the phase morphologies under quiescent and annealed conditions. Electromagnetic interference (EMI) shielding effectiveness in X and K-u-band frequencies were measured to explore these composites for EMI shielding applications. Interestingly, MWNT-II showed the highest electrical conductivity and EMI shielding in the blends.