Conference Papers

Permanent URI for this collectionhttps://idr.nitk.ac.in/handle/123456789/28506

Browse

Subject: search.filters.subject.Graph Theory

Search Results

Now showing 1 - 3 of 3
  • No Thumbnail Available
    Item
    Comparative analysis of Vertex Cover computation algorithms for varied graphs
    (Institute of Electrical and Electronics Engineers Inc., 2014) Patel, S.; Kamath S․, S.
    There are several vertex cover algorithms proposed for the solution of well-known NP-complete class problem of computing vertex cover. The Vertex Cover problem is important to address as it has various real world applications viz. Wireless Communication Network, Airline Communication Network, Terrorist Communication Network, etc. In this paper, we present a comparative evaluation of different existing algorithms like approximation, list, greedy and Alom's for most efficiently computing vertex cover over a variety of large graphs. Our empirical study found that Alom's algorithm performs consistently better than the other algorithms for all types of graphs, regardless of their class and number of vertices in the graph, while approximation algorithms show the worst performance for very large graphs. © 2014 IEEE.
  • No Thumbnail Available
    Item
    K-distinct strong minimum energy topology problem in wireless sensor networks
    (Springer Verlag, 2015) Panda, B.S.; Shetty D, D.P.; Pandey, A.
    Given a set of sensors, the strong minimum energy topology (SMET) problem is to assign transmit power to each sensor such that the resulting topology containing only bidirectional links is strongly connected and the total energy of all the nodes is minimized. The SMET problem is known to be NP-hard. Currently available sensors in the market support a finite set of transmission ranges. So we consider the k- Distinct-SMET problem, where only k transmission power levels are used. We prove that the k-Distinct-SMET problem is NP-complete for k ≥ 3. However, on the positive side, we show that the 2-Distinct- SMET problem can be solved in polynomial time. The energy cost of transmitting a bit is higher than the cost of computation, and hence it may be advantageous to organize the sensors into clusters and form a hierarchical structure. This motivated the study of k-Distinct-rStrong Minimum Energy Hierarchical Topology (k-Distinct-rSMEHT) problem: Given a sensor network consisting of n sensors, and integers k and r, assign transmit powers to all sensors out of the k distinct power levels such that (i) the graph induced using only the bi-directional links is connected, (ii) at most r sensors are connected to two or more sensors by a bidirectional link and (iii) the sum of the transmit powers of all the sensors is minimum. We Propose a(formula presented.) approximation algorithm for the k-Distinct-rSMEHT problem for any fixed r and arbitrary k. © Springer International Publishing Switzerland 2015.
  • No Thumbnail Available
    Item
    Indian Postal Service Quality Assessment Using Graph Theoretic Approach – A Quantitative Decision-Making Tool
    (Springer Science and Business Media Deutschland GmbH, 2023) Vadivel, S.M.; Sequeira, A.H.; Jauhar, S.K.
    This research intends to examine the Service Quality (SQ) factors in mail service operations conducted at National Sorting Hub (NSH), Mangalore, Karnataka state, Southern India. In the postal service industry, measuring SQ performance in mail service operations is a major challenge. So, this paper attempts to explore the positive effect of postal SQ factors on Customer Satisfaction (CS) with the data collected from employees (n = 148) to the Indian postal service. Further, to quantify the significance of SQ factors in gaining customer satisfaction, this study has used Graph-Theoretic approach technique. Results established same priority index to the SQ factors such as Human service delivery (Rank 1), Core service (Rank 2), and Systemization (Rank 3). The results indicate that the postal service industry should concentrate more on these factors to enhance their customer satisfaction. Further, the study employs the operating empirical model which is sparsely used in Indian domain. Furthermore, this research aids the SQ in designing and developing the necessary aspects to improve the CS in various service sectors. © 2023, The Author(s), under exclusive license to Springer Nature Switzerland AG.