Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

A simple local 3-approximation algorithm for vertex cover

We present a local algorithm (constant-time distributed algorithm) for finding a 3-approximate vertex cover in bounded-degree graphs. The algorithm is deterministic, and no auxiliary information besides port numbering is required. (c) 2009 Elsevier B.V. All rights reserved.

A local 2-approximation algorithm for the vertex cover problem

We present a distributed 2-approximation algorithm for the minimum vertex cover problem. The algorithm is deterministic, and it runs in (Δ + 1)2 synchronous communication rounds, where Δ is the maximum degree of the graph. For Δ = 3, we give a 2-approximation algorithm also for the weighted version of the problem.

Mining Land Cover Information Using Multilayer Perceptron and Decision Tree from MODIS Data

Land cover (LC) changes play a major role in global as well as at regional scale patterns of the climate and biogeochemistry of the Earth system. LC information presents critical insights in understanding of Earth surface phenomena, particularly useful when obtained synoptically from remote sensing data. However, for developing countries and those with large geographical extent, regular LC mapping is prohibitive with data from commercial sensors (high cost factor) of limited spatial coverage (low temporal resolution and band swath). In this context, free MODIS data with good spectro-temporal resolution meet the purpose. LC mapping from these data has continuously evolved with advances in classification algorithms. This paper presents a comparative study of two robust data mining techniques, the multilayer perceptron (MLP) and decision tree (DT) on different products of MODIS data corresponding to Kolar district, Karnataka, India. The MODIS classified images when compared at three different spatial scales (at district level, taluk level and pixel level) shows that MLP based classification on minimum noise fraction components on MODIS 36 bands provide the most accurate LC mapping with 86% accuracy, while DT on MODIS 36 bands principal components leads to less accurate classification (69%).

A note on surface water waves for finite depth in the presence of an ice-cover

A class of I boundary value problems involving propagation of two-dimensional surface water waves, associated with water of uniform finite depth, against a plane vertical wave maker is investigated under the assumption that the surface is covered by a thin sheet of ice. It is assumed that the ice-cover behaves like a thin isotropic elastic plate. Then the problems under consideration lead to those of solving the two-dimensional Laplace equation in a semi-infinite strip, under Neumann boundary conditions on the vertical boundary as well as on one of the horizontal boundaries, representing the bottom of the fluid region, and a condition involving upto fifth order derivatives of the unknown function on the top horizontal ice-covered boundary, along with the two appropriate edge-conditions, at the ice-covered corner, ensuring the uniqueness of the solutions. The mixed boundary value problems are solved completely, by exploiting the regularity property of the Fourier cosine transform.

Contrained linear spectral unmixing technique for regional land cover mapping using MODIS data

Over the last few decades, there has been a significant land cover (LC) change across the globe due to the increasing demand of the burgeoning population and urban sprawl. In order to take account of the change, there is a need for accurate and up- to-date LC maps. Mapping and monitoring of LC in India is being carried out at national level using multi-temporal IRS AWiFS data. Multispectral data such as IKONOS, Landsat- TM/ETM+, IRS-1C/D LISS-III/IV, AWiFS and SPOT-5, etc. have adequate spatial resolution (~ 1m to 56m) for LC mapping to generate 1:50,000 maps. However, for developing countries and those with large geographical extent, seasonal LC mapping is prohibitive with data from commercial sensors of limited spatial coverage. Superspectral data from the MODIS sensor are freely available, have better temporal (8 day composites) and spectral information. MODIS pixels typically contain a mixture of various LC types (due to coarse spatial resolution of 250, 500 and 1000 m), especially in more fragmented landscapes. In this context, linear spectral unmixing would be useful for mapping patchy land covers, such as those that characterise much of the Indian subcontinent. This work evaluates the existing unmixing technique for LC mapping using MODIS data, using end- members that are extracted through Pixel Purity Index (PPI), Scatter plot and N-dimensional visualisation. The abundance maps were generated for agriculture, built up, forest, plantations, waste land/others and water bodies. The assessment of the results using ground truth and a LISS-III classified map shows 86% overall accuracy, suggesting the potential for broad-scale applicability of the technique with superspectral data for natural resource planning and inventory applications.

Land Surface Temperature with Land Cover Dynamics:Multi-Resolution, Spatio-Temporal Data Analysis of Greater Bangalore

Bangalore is experiencing unprecedented urbanisation in recent times due to concentrated developmental activities with impetus on IT (Information Technology) and BT (Biotechnology) sectors. The concentrated developmental activities has resulted in the increase in population and consequent pressure on infrastructure, natural resources, ultimately giving rise to a plethora of serious challenges such as urban flooding, climate change, etc. One of the perceived impact at local levels is the increase in sensible heat flux from the land surface to the atmosphere, which is also referred as heat island effect. In this communication, we report the changes in land surface temperature (LST) with respect to land cover changes during 1973 to 2007. A novel technique combining the information from sub-pixel class proportions with information from classified image (using signatures of the respective classes collected from the ground) has been used to achieve more reliable classification. The analysis showed positive correlation with the increase in paved surfaces and LST. 466% increase in paved surfaces (buildings, roads, etc.) has lead to the increase in LST by about 2 ºC during the last 2 decades, confirming urban heat island phenomenon. LSTs’ were relatively lower (~ 4 to 7 ºC) at land uses such as vegetation (parks/forests) and water bodies which act as heat sinks.

Changes in seasonal snow cover in Hindu Kush-Himalayan region

The changes in seasonal snow covered area in the Hindu Kush-Himalayan (HKH) region have been examined using Moderate – resolution Imaging Spectroradiometer (MODIS) 8-day standard snow products. The average snow covered area of the HKH region based on satellite data from 2000 to 2010 is 0.76 million km2 which is 18.23% of the total geographical area of the region. The linear trend in annual snow cover from 2000 to 2010 is −1.25±1.13%. This is in consistent with earlier reported decline of the decade from 1990 to 2001. A similar trend for western, central and eastern HKH region is 8.55±1.70%, +1.66% ± 2.26% and 0.82±2.50%, respectively. The snow covered area in spring for HKH region indicates a declining trend (−1.04±0.97%). The amount of annual snowfall is correlated with annual seasonal snow cover for the western Himalaya, indicating that changes in snow cover are primarily due to interannual variations in circulation patterns. Snow cover trends over a decade were also found to vary across seasonally and the region. Snow cover trends for western HKH are positive for all seasons. In central HKH the trend is positive (+15.53±5.69%) in autumn and negative (−03.68±3.01) in winter. In eastern HKH the trend is positive in summer (+3.35±1.62%) and autumn (+7.74±5.84%). The eastern and western region of HKH has an increasing trend of 10% to 12%, while the central region has a declining trend of 12% to 14% in the decade between 2000 and 2010. Snow cover depletion curve plotted for the hydrological year 2000–2001 reveal peaks in the month of February with subsidiary peaks observed in November and December in all three regions of the HKH.

Monitoring of seasonal snow cover in Bhutan using remote sensing technique

All major rivers in Bhutan depend on snowmelt for discharge. Therefore, changes in snow cover due to climate change can influence distribution and availability of water. However, information about distribution of seasonal snow cover in Bhutan is not available. The MODIS snow product was used to study snow cover status and trends in Bhutan. Average snow cover area (SCA) of Bhutan estimated for the period 2002 to 2010 was 9030 sq. km, about 25.5% of the total land area. SCA trend of Bhutan for the period 2002-2010 was found to decrease (-3.27 +/- 1.28%). The average SCA for winter was 14,485 sq. km (37.7%), for spring 7411 sq. km (19.3%), for summer 4326 sq. km (11.2%), and for autumn 7788 sq. km (20.2%), mostly distributed in the elevation range 2500-6000 m amsl. Interannual and seasonal SCA trend both showed a decline, although it was not statistically significant for all sub-basins. Pho Chu sub-basin with 19.5% of the total average SCA had the highest average SCA. The rate of increase of SCA for every 100 m elevation was the highest (2.5%) in the Pa Chu sub-basin. The coefficient of variance of 1.27 indicates high variability of SCA in winter.