A Note on Decision versus Search for Graph Automorphism

We show that for any graphG,knontrivial automorphisms ofG—if as many exist—can be computed in time |G|^{O(log k)}with nonadaptive queries to GA, the decision problem for Graph Automorphism. As a consequence, we show that some problems related to GA are actually polynomial-time truth-table equivalent to GA. One of these results provides an answer to an open question of Lubiw [SIAM J. Comput.10(1981), 11–21].     

Reinterpretable Imager: Towards Variable Post‐Capture Space,Angle and Time Resolution in Photography

We describe a novel multiplexing approach to achieve tradeoffs in space, angle and time resolution in photography. We explore the problem of mapping useful subsets of time‐varying 4D lightfields in a single snapshot. Our design is based on using a dynamic mask in the aperture and a static mask close to the sensor. The key idea is to exploit scene‐specific redundancy along spatial, angular and temporal dimensions and to provide a programmable or variable resolution tradeoff among these dimensions. This allows a user to reinterpret the single captured photo as either a high spatial resolution image, a refocusable image stack or a video for different parts of the scene in post‐processing. A lightfield camera or a video camera forces a‐priori choice in space‐angle‐time resolution. We demonstrate a single prototype which provides flexible post‐capture abilities not possible using either a single‐shot lightfield camera or a multi‐frame video camera. We show several novel results including digital refocusing on objects moving in depth and capturing multiple facial expressions in a single photo.     

Inventory model for seasonal demand with option to change the market

In real life, when bulk purchase becomes convenient or even mandatory, it is a common practice for distributors to explore an alternative market in order to maximize the revenue earned. In this paper, we consider an inventory model for a product having seasonal demand with two potential markets, say, primary and alternate. The distributor has a single opportunity of procurement prior to multiple demand seasons in the primary and the alternate market. Both the markets have similar demand patterns, with time lag between their demand seasons. The demand is a price and time dependent function with increasing, constant and declining phases within each demand season. The scale parameter of demand rate depends upon the market. In each market, successive seasons are separated by random time. In one replenishment cycle, the distributor has a single option to exit the primary market by transferring the inventory, with or without change in selling price. This option can be exercised at the end of any complete season at the primary market. Our investigations indicate that it will be beneficial for the distributor to shift to the alternate market even at a slightly lower selling price if demand rate in the alternate market is higher. Optimal number of seasons at the primary market before change of price or market is obtained. Optimal policy is obtained for jointly determining the order quantity and price. Concavity of the profit function is discussed. Solution procedure, numerical examples and sensitivity analysis are presented.     

Polynomial based scheme (PBS) for establishing Authentic Associations in Wireless Mesh Networks

The varying degree of mobility of Mesh Clients has provided much more flexibility in Wireless Mesh Networks, and establishing an Authentic Association among entities is a non-trivial problem. In this paper, we introduce a Polynomial Based scheme which provides pair-wise connectivity, low communication, marginal storage overhead and high scalability while making on the fly Authentic Association feasible. The proposed scheme is also observed to be resilient against both traffic analysis and node capture attacks.     

Impact of a simple load balancing approach and an incentive-based scheme on MANET performance

Most reactive mobile ad hoc network (MANET) routing protocols such as AODV and DSR do not perform search for new routes until the network topology changes. But, low node mobility does not affect the MANET connectivity and the same routes may be used for a long time. This may cause concentration of traffic on few mobile stations (MSs), which results in congestion and hence longer end-to-end delay. In addition, continuous use of MSs may cause their battery power to get exhausted rapidly. Expiration of MS energy causes disruption of connections traversing through the MSs and could generate many simultaneous new routing requests. Therefore, we propose a load balancing approach called Simple Load Balancing Approach (SLBA), which can be transparently added to any current reactive routing protocol such as AODV and DSR. SLBA minimizes the traffic concentration by allowing each MS to drop RREQ or to give up packet forwarding depending on its own traffic load. Meanwhile, MSs may deliberately give up forwarding packets to save their own energy. For encouraging MSs to volunteer in forwarding packets, we introduce a reward scheme for packet forwarding, named Protocol-Independent Fairness Algorithm (PIFA). We compare the performance of AODV and DSR with and without SLBA and PIFA. Simulation results indicate that SLBA can distribute traffic very well and improve the MANET performance. PIFA is also observed to prevent MANET partitioning and any performance degradation due to selfish nodes.     

Perimeter discovery in wireless sensor networks

In this paper, we focus on the perimeter detection problem using wireless sensor networks, as perimeter detection has a wide range of uses in several areas. We present a decentralized localized algorithm where sensor nodes determine if they are located along the perimeter of a wireless sensor network. Our proposed algorithm uses the location neighborhood information in conjunction with the Barycentric technique to determine if the sensor node enclosed by neighboring nodes, and consequently, if it is located within the interior of the wireless sensor network. We define performance metrics to analyze the performance of our approach and the simulation shows that the algorithm gives fairly accurate results.     

Structural modelling and integrative analysis of microelectromechanical systems product using graph theoretic approach

Micro-electromechanical systems (MEMS) as an enabling technology is seen to play a more and more important role for the main stream of industry of the future by broadening its applications to information, communications and bio technologies. Development of MEMS devices, however, still relies on knowledge and experience of MEMS experts due to the design and fabrication process complexity. It is difficult to understand the trade-offs inherent in the system and achieve an optimal structure without any MEMS-related insight. An attempt is made to develop an integrated systems model for the complete structure of the MEMS product system in terms of its constituents and interactions between the constituents. The hierarchical tree structures of the MEMS system and its subsystems are presented up to component level. For characterization, analysis and identification of MEMS product system, three different mathematical models say graph theoretic model, matrix model and permanent model are presented. These models are associated with graph theory, matrix method and variable permanent function by considering the various subsystems, subsubsystems up to component level, their connectivity and interdependency of the MEMS product system. The developed methodology is explained with an example. The proposed modeling and analysis is extendable to the subsystems and the component level. An overall structural analysis can be carried out by following a ‘top-down’ approach or ‘bottom-up’ approach. Understanding of MEMS product structure will help in the improvement of performance, cost, design time, and so on.     

Analysis of weight distribution strategies in unilateral transtibial amputees during the stand-to-sit activity.

Current methods of quantifying the stand-to-sit activity (StTS) are resource intensive and have not been applied to unilateral transtibial amputees (TTAs). The purpose of this study is to define five phases of arm-rest assisted and unassisted StTS using simple instrumentation and implement this method for assessing TTA movement patterns. Twelve TTAs and 12 age-matched non-amputees performed StTS with and without arm-rest support. Symmetry of weight distribution between lower limbs was calculated for five StTS phases: Descent Initiation; Descent Deceleration; Seat-Contact; Stabilisation and Sitting. TTAs demonstrated an asymmetrical weight distribution pattern and a tendency to transfer weight to the intact limb during the course of the activity. Non-amputees had relatively higher symmetry and did not exhibit substantial weight shifts during the activity. Symmetry indices were similar for assisted and unassisted sitting in both subject groups. These results highlight a need for therapeutic interventions in TTAs for reducing loading asymmetries and associated co-morbidities.