Faculty Publications
Permanent URI for this communityhttps://idr.nitk.ac.in/handle/123456789/18736
Publications by NITK Faculty
Browse
19 results
Search Results
Item A Privacy Preserved Data Mining Approach Based on k-Partite Graph Theory(Elsevier, 2015) Bhat, T.P.; Karthik, C.; Chandrasekaran, K.Traditional approaches to data mining may perform well on extraction of information necessary to build a classification rule useful for further categorisation in supervised classification learning problems. However most of the approaches require fail to hide the identity of the subject to whom the data pertains to, and this can cause a big privacy breach. This document addresses this issue by the use of a graph theoretical approach based on k-partitioning of graphs, which paves way to creation of a complex decision tree classifier, organised in a prioritised hierarchy. Experimental results and analytical treatment to justify the correctness of the approach are also included. © 2015 The Authors.Item Algorithms for minimizing the receiver interference in a wireless sensor network(Institute of Electrical and Electronics Engineers Inc., 2016) Shetty D, D.P.; Lakshmi, M.P.Limiting Interference between the nodes in a Wireless Sensor Network (WSN) is of considerable importance for energy-efficiency of the network. Minimizing the interference in a WSN minimizes the overall energy consumption of the network by reducing the number of conflicting transmissions. We consider Receiver interference minimization problem. Two types of interference are defined in a WSN, namely Sender interference and Receiver interference. In this paper we consider the Receiver interference problem, where the objective is to minimize the maximum Receiver interference. The problem of minimizing the maximum Receiver interference is proved to be NP-hard. In this paper we propose two algorithms named MinMax-RIP and a modified version of the same to minimize the maximum Receiver interference in a WSN. We evaluate the performance of our algorithms through simulation. We then consider the interference minimization problem in a broadcast network. We propose MinMax-BRIP algorithm for optimal range assignment which gives minimum total Receiver interference for connectivity predicate Broadcast. © 2016 IEEE.Item Optimizing set of paths connecting multiple source-sink pairs(Institute of Electrical and Electronics Engineers Inc., 2017) Agrawal, A.; Dixit, B.; Karve, V.U.; Chandavarkar, B.R.In this paper we aim to propose an algorithm for finding the most optimal path with some must-include nodes. The algorithm will be used to look for the best path that includes all the required nodes arranged in static topology in the most cost efficient way while keeping in mind the given constraint. We have developed the algorithm for nodes, where information about all nearby nodes is available beforehand. The main aim of the algorithm is to get the optimal paths between nodes with the given constraints. After getting all optimal paths, the algorithm will use a heuristic function to determine the best path out of the all paths as the final path. The main aim of our proposed methodology is to minimize the input resources to achieve the maximum output. For doing this we have proposed a method to combine multiple paths from a source to sink in one single optimal path, thus reducing the number of paths and achieving the same output. For developing this algorithm we have used concepts of graph theory, combinatorial optimizations and well known approach of Knuth for finding exact cover for given graph. © 2016 IEEE.Item On strong (weak) independent sets and vertex coverings of a graph(2007) Kamath, S.S.; Bhat, R.S.A vertex v in a graph G = (V, E) is strong (weak) if deg (v) ? deg (u)(deg (v) ? deg (u)) for every u adjacent to v in G. A set S ? V is said to be strong (weak) if every vertex in S is a strong (weak) vertex in G. A strong (weak) set which is independent is called a strong independent set [SIS] (weak independent set [WIS]). The strong (weak) independence numbers ? = s ? (G) (w ? = w ? (G)) is the maximum cardinality of an SIS (WIS). For an edge x = uv, v strongly covers the edge x if deg (v) ? deg (u) in G. Then u weakly covers x. A set S ? V is a strong vertex cover [SVC] (weak vertex cover [WVC]) if every edge in G is strongly (weakly) covered by some vertex in S. The strong (weak) vertex covering numbers ? = s ? (G)(w ? = w ? (G)) is the minimum cardinality of an SVC (WVC). In this paper, we investigate some relationships among these four new parameters. For any graph G without isolated vertices, we show that the following inequality chains hold: s ? ? ? ? s ? ? w ? and s ? ? w ? ? ? ? w ?. Analogous to Gallai's theorem, we prove s ? + w ? = p and w ? + s ? = p. Further, we show that s ? ? p - ? and w ? ? p - ? and find a necessary and sufficient condition to attain the upper bound, characterizing the graphs which attain these bounds. Several Nordhaus-Gaddum-type results and a Vizing-type result are also established. © 2006.Item Strongly indexable graphs and applications(2009) Hegde, S.M.; Shetty, S.In 1990, Acharya and Hegde introduced the concept of strongly k-indexable graphs: A (p, q)-graph G = (V, E) is said to be stronglyk -indexable if its vertices can be assigned distinct numbers 0, 1, 2, ..., p - 1 so that the values of the edges, obtained as the sums of the numbers assigned to their end vertices form an arithmetic progression k, k + 1, k + 2, ..., k + (q - 1). When k = 1, a strongly k-indexable graph is simply called a strongly indexable graph. In this paper, we report some results on strongly k-indexable graphs and give an application of strongly k-indexable graphs to plane geometry, viz; construction of polygons of same internal angles and sides of distinct lengths. © 2009 Elsevier B.V. All rights reserved.Item Distributed load flow analysis using graph theory(2011) Sharma, D.P.; Chaturvedi, A.; Purohit, G.; Shivarudraswamy, R.In today scenario, to meet enhanced demand imposed by domestic, commercial and industrial consumers, various operational & control activities of Radial Distribution Network (RDN) requires a focused attention. Irrespective of sub-domains research aspects of RDN like network reconfiguration, reactive power compensation and economic load scheduling etc, network performance parameters are usually estimated by an iterative process and is commonly known as load (power) flow algorithm. In this paper, a simple mechanism is presented to implement the load flow analysis (LFA) algorithm. The reported algorithm utilizes graph theory principles and is tested on a 69- bus RDN.Item Distributed load flow analysis using graph theory(2011) Sharma, D.P.; Chaturvedi, A.; Purohit, G.; Shivarudraswamy, R.In today scenario, to meet enhanced demand imposed by domestic, commercial and industrial consumers, various operational & control activities of Radial Distribution Network (RDN) requires a focused attention. Irrespective of sub-domains research aspects of RDN like network reconfiguration, reactive power compensation and economic load scheduling etc, network performance parameters are usually estimated by an iterative process and is commonly known as load (power) flow algorithm. In this paper, a simple mechanism is presented to implement the load flow analysis (LFA) algorithm. The reported algorithm utilizes graph theory principles and is tested on a 69- bus RDN.Item Incorporating local image structure in normalized cut based graph partitioning for grouping of pixels(2013) Sen, D.; Gupta, N.; Pal, S.K.Graph partitioning for grouping of image pixels has been explored a lot, with normalized cut based graph partitioning being one of the popular ones. In order to have a credible allegiance to the perceptual grouping taking place in early human vision, we propose and study in this paper the incorporation of local image structure/context in normalized cut based graph partitioning for grouping of image pixels. Similarity and proximity, which have been studied earlier for grouping of image pixels, are only two among many perceptual cues that act during grouping in early human vision. In addition to the said two cues, we study three other such cues, namely, common fate, common region and continuity, and find indications of local image structure utilization during grouping of image pixels. Appropriate incorporation of local image structure/context is achieved by representing it using neighborhood in the form of histogram and fuzzy set. We demonstrate both qualitatively and quantitatively through experimental results that the incorporation of local image structure improves performance of grouping of image pixels. © 2013 Elsevier Inc. All rights reserved.Item Separation Dimension of Graphs and Hypergraphs(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.Separation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.Item Maximal Induced Matchings in Triangle-Free Graphs(Wiley-Liss Inc. info@wiley.com, 2016) Basavaraju, M.; Heggernes, P.; van 't'Hof, P.; Saei, R.; Villanger, Y.An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most (Formula presented.) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most (Formula presented.) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3, 3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time (Formula presented.), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. © 2015 Wiley Periodicals, Inc.