Search Results

Now showing 1 - 6 of 6

Open Access
Study of Total Graph Using Dynamic Graph Operation
(Dhirubhai Ambani Institute of Information and Communication Technology, 2017) Patel, Dhaval; Muthu, Rahul
"Auxiliary graphs are graphs which are used to translate one graph problem to another graph problem. Total graph is also an auxiliary graph which is used to translate the total coloring problem into the vertex coloring problem. Dynamic graph operation on a graph is defined as sequence of update operation on the graph, where update operations are add vertex/edge and remove edge/vertex. This thesis derives some new characteristics of total graph. By using existing properties and new properties, we have developed algorithms to find maximal total sub graph of an arbitrary nontotal graph. We have devised a procedure by using which we are able tomigrate set of edges form vertex-vertex part to edgevertex part, together with some allied operations such that the resulting graph is also a total graph. For super total graph we have provided some characteristics which is required to add a vertex/edge."
Open Access
Study on shock graphs: graph representation of objects
(Dhirubhai Ambani Institute of Information and Communication Technology, 2013) Desai, Abhi Hitesh; Tatu, Aditya; Sunitha, V.
A shock graph is an abstraction of a two-dimensional shape of an object. It represents the shape as a graph, using its boundary information. In this thesis, we study the shock graph representation of two-dimensional shapes. We discuss a method to compute an approximation of shock graph. We discuss different thresholds we need to set for shock graph computation, and some solutions on how we can get rid of them in some cases. Next, we see the results showing some unique properties of shock graph. And finally, we discuss how we can use shock graphs in different applications, and for further research.
Open Access
Acyclic edge coloring of complete r-partite graphs
(Dhirubhai Ambani Institute of Information and Communication Technology, 2011) Teja, V. Krishna; Muthu, Rahul
An acyclic edge coloring of a graph G is a proper edge coloring of G which has no dichromatic cycle. The minimum number of colors required to acyclically edge color graph G is called its acyclic chromatic index, denoted a’ (G). In this thesis, we present an acyclic edge coloring for complete graphs Ka, b, where a>b and a is prime, using Δ (G) =a colors. An acyclic edge coloring for complete tripartite graphs, and r-partite graphs (r>3) is presented. These colorings follow patterns similar to those used in the case of complet bipartite graphs.
Open Access
Path complexity of the class binary search tree
(Dhirubhai Ambani Institute of Information and Communication Technology, 2009) Doshi, Nishant; Amin, Ashok T.
Path complexity of a program is defined as the number of program execution paths as a function of input size n. This notion of program complexity has been extended to complexity of a class as follows. Class had data members and data operations. The notion of state for the class is defined based on structural representation of a class. We are assuming only those data operations that change state of a class. The path complexity of a class is defined to be the number of valid input sequences, each of them containing n data operations. We have analyzed the path complexity of the class Binary Search Tree (BST) based on the algorithms for insert and delete data operations. Later we modify program for delete operation to facilitate determination of path complexity for the class BST. The bounds for the path complexity of the class BST are determined. A program is developed to obtain path complexity of the class BST.
Open Access
Path complexity of maximum segment sum problem
(Dhirubhai Ambani Institute of Information and Communication Technology, 2009) Mishra, Devesh; Amin, Ashok T.
Various software complexity metrics have been proposed in literature. A program complexity measure called path complexity is proposed in [1]. Path complexity P(A,n) of an algorithm A is defined to be the number of program execution paths of A over all inputs of size n. It defines a partition of input space of program A into equivalence classes on the basis of different program execution paths. All the inputs belonging to an equivalence class are equivalent to each other in a sense that they follow same execution path. We present path complexity analysis of four different algorithms for one-dimensional maximum segment sum problem which shows that algorithms with different computational complexity may be equivalent to each other in their path complexity. We also present lower bounds on one dimensional as well as two dimensional maximum segment-sum problems. A different perspective and several observations on one dimensional problem are given
Open Access
On path complexities of heapsort algorithm and the class stack
(Dhirubhai Ambani Institute of Information and Communication Technology, 2007) Mangal, Anupam; Amin, Ashok T.
A measure of program complexity, called Path Complexity, based on the number of program execution paths as a function of the input size n, is proposed in [AJ05]. This measure can be used to compare the complexity of two different programs even with isomorphic control flow graphs. Using this measure, we determine the path complexity of the Heapsort algorithm. The notion of path complexity of a program is further extended to introduce the path complexity of a class. In particular, the path complexity of the Stack class is determined. We also provide an upper bound, and a lower bound based on catalan numbers, on the path complexity of the Stack class.

M Tech Dissertations

Browse

Filters

Settings

Sort By

Results per page

Search Results