Various civil and military applications of UAVs, or ground robots, require a set of vehicles to monitor a group of targets. Routing problems naturally arise in this setting where the operators of the vehicles have to plan the paths suitably in order to optimize the use of resources available such as sensors, fuel etc. These vehicles may differ either in their structural (design and dynamics) or functional (sensing) capabilities. This thesis addresses an important routing problem involving two heterogeneous vehicles. As the addressed routing problem is NP-Hard, we develop an approximation algorithm and heuristics to solve the problem. Our approach involves dividing the routing problem into two sub-problems: Partitioning and Sequencing. Partitioning the targets involves finding two distinct sets of targets, each corresponding to one of the vehicles. We then find a sequence in which these targets need to be visited in order to optimize the use of resources to the maximum possible extent. The sequencing problem can be solved either by Christofides algorithm or the Lin-Kernighan Heuristic (LKH). The problem of partitioning is tackled by solving a Linear Program (LP) obtained by relaxing some of the constraints of an Integer Programming (IP) model for the problem. We observe the performance of two LP models for the partitioning. The first LP model is obtained by relaxing only the integrality constraints whereas in the second model relaxes both integrality and degree constraints. The algorithms were implemented in a C++ environment with the help of Concert Technology for CPLEX, and Boost Graph Libraries. The performance of these algorithms was studied for 50 random instances of varying problem sizes. It was found that on an average, the algorithms based on the first LP model provided better (closer to the optimum) solutions as compared to those based on the second LP model. We also observed that for both the LP models, the average quality of solutions given by the heuristics were found to be better ( within 5% of the optimum) than the average quality of solutions obtained from the approximation algorithm (between 30 - 60% of the optimum depending on the problem size).

A grid graph is a finite embedded subgraph of the infinite integer grid. A solid grid graph is a grid graph without holes, i.e., each bounded face of the graph is a unit square. The reconfiguration problem for Hamiltonian cycle or path in a sold grid graph G asks the following question: given two Hamiltonian cycles (or paths) of G, can we transform one cycle (or path) to the other using some "operation" such that we get a Hamiltonian cycle (or path) of G in the intermediate steps (i.e., after each application of the operation)? In this thesis, we investigate reconfiguration problems for Hamiltonian cycles and paths in the context of two types of solid graphs: rectangular grid graphs, which have a rectangular outer boundary, and L- shaped grid graphs, which have a single reflex corner on the outer boundary, under three operations we define, flip, transpose and switch, that are local in the grid. Reconfiguration of Hamiltonian cycles and paths in embedded grid graphs has potential applications in path planning, robot navigation, minimizing turn costs in milling problems, minimizing angle costs in TSP, additive manufacturing and 3D printing, and in polymer science. In this thesis, we introduce a complexity measure called bend complexity for Hamiltonian paths and cycles in grid graphs, and using those measures we measure complexity of a grid graph G and give upper and lower bounds on the maximum bend complexity of an mxn grid graph. We define three local operations, flip, transpose and switch, where local means that the operations are applied on vertices that are close in the grid graph but may not be close on the path or cycle. We show that any Hamiltonian cycle or path can be reconfigured to any other Hamiltonian cycle or path in an mxn rectangular grid graph, where m <= 4, using O(|G|) flips and transposes, regardless of the bend complexities of the two cycles. We give algorithms to reconfigure 1-complex Hamiltonian cycles in a rectangular or L-shaped grid graph G using O(|G|) flips and transposes, where the intermediate steps are also 1-complex Hamiltonian cycles. Finally, we establish the structure of 1-complex Hamiltonian paths between diagonally opposite corners s and t of a rectangular grid graph, and then provide a strategy, based on work in progress, for designing an algorithm to reconfigure between any two 1-complex s, t Hamiltonian paths using switch operations. / Graduate

This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.

In this dissertation, the problem of planning the motion of m Unmanned Vehicles (UVs) (or simply vehicles) through n points in a plane is considered. A motion plan for a vehicle is given by the sequence of points and the corresponding angles at which each point must be visited by the vehicle. We require that each vehicle return to the same initial location(depot) at the same heading after visiting the points. The objective of the motion planning problem is to choose at most q(≤ m) UVs and find their motion plans so that all the points are visited and the total cost of the tours of the chosen vehicles is a minimum amongst all the possible choices of vehicles and their tours. This problem is a generalization of the wellknown Traveling Salesman Problem (TSP) in many ways: (1) each UV takes the role of salesman (2) motion constraints of the UVs play an important role in determining the cost of travel between any two locations; in fact, the cost of the travel between any two locations depends on direction of travel along with the heading at the origin and destination, and (3) there is an additional combinatorial complexity stemming from the need to partition the points to be visited by each UV and the set of UVs that must be employed by the mission. In this dissertation, a sub-optimal, two-step approach to motion planning is presented to solve this problem:(1) the combinatorial problem of choosing the vehicles and their associated tours is based on Euclidean distances between points and (2) once the sequence of points to be visited is specified, the heading at each point is determined based on a Dynamic Programming scheme. The solution to the first step is based on a generalization of Held-Karp’s method. We modify the Lagrangian heuristics for finding a close sub-optimal solution. In the later chapters of the dissertation, we relax the assumption that all vehicles are homogenous. The motivation of heterogenous variant of Multi-depot, Multiple Traveling Salesmen Problem (MDMTSP) derives form applications involving Unmanned Aerial Vehicles (UAVs) or ground robots requiring multiple vehicles with different capabilities to visit a set of locations.

A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. / Mathematical Sciences / PHD (MATHEMATICS)

A graph G is maximal nontraceable (MNT) (maximal nonhamiltonian (MNH)) if G is not traceable (hamiltonian), i.e. does not contain a hamiltonian path (cycle), but G+xy is traceable (hamiltonian) for all nonadjacent vertices x and y in G. A graph G is hypohamiltonian if G is not hamiltonian, but every vertex deleted subgraph G -u of G is hamiltonian. A graph which is maximal nonhamiltonian and hypohamiltonian is called maximal hypohamiltonian (MHH). Until recently, not much has appeared in the literature about MNT graphs, although there is an extensive literature on MNH graphs. In 1998 Zelinka constructed two classes of MNT graphs and made the conjecture, which he later retracted, that every MNT graph belongs to one of these classes. We show that there are many different types of MNT graphs that cannot be constructed by Zelinka's methods. Although we have not been able to characterize MNT graphs in general, our attempt at characterizing MNT graphs with a specified number of blocks and cut-vertices enabled us to construct infinite families of non-Zelinka MNT graphs which have either two or three blocks. We consider MNT graphs with toughness less than one, obtaining results leading to interesting constructions of MNT graphs, some based on MHH graphs. One result led us to discover a non-Zelinka MNT graph of smallest order, namely of order 8. We also present examples of MNTgraphs with toughness at least one, including an infinite family of 2-connected, claw-free graphs. We find a lower bound for the size of 2-connected MNT graphs of order n. We construct an infinite family of 2-connected cubic MNT graphs of order n, using MHH graphs as building blocks. We thus find the minimum size of 2-connected MNT graphs for infinitely many values of n. We also present a construction, based on MHH graphs, of an infinite family of MNT graphs that are almost cubic. We establish the minimum size of MNT graphs of order n, for all except 26 values of n, and we present a table of MNT graphs of possible smallest size for the excluded 26 values of n. / Mathematical Sciences / PHD (MATHEMATICS)

This thesis focuses on the design and implementation of an application involving the principles of DNA computing simulation for solving some selected problems. DNA computing represents an unconventional computing paradigm that is totally different from the concept of electronic computers. The main idea of DNA computing is to interpret the DNA as a medium for performing computation. Despite the fact, that DNA reactions are slower than operations performed on computers, they may provide some promising features in the future. The DNA operations are based on two important aspects: massive parallelism and principle of complementarity. There are many important problems for which there is no algorithm that would be able to solve the problem in a polynomial time using conventional computers. Therefore, the solutions of such problems are searched by exploring the entire state space. In this case the massive parallelism of the DNA operations becomes very important in order to reduce the complexity of finding a solution.

Path integral approaches have been widely used for long in both quantum mechanics as well as statistical mechanics. In addition to being a tool for obtaining the probability distributions of interest(wave functions in the case of quantum mechanics),these methods are very instructive and offer great insights into the problem. In this thesis, path integrals are extensively employed to study some very interesting problems in both equilibrium and non-equilibrium statistical mechanics. In the non-equilibrium regime, we have studied, using a path integral approach, a very interesting class of anomalous diffusion, viz. the L´evy flights. In equilibrium statistical mechanics, we have evaluated the partition function for a class of molecules referred to as the hindered rotors which have a barrier for internal rotation. Also, we have evaluated the exact quantum statistical mechanical propagator for a harmonic potential with a time-dependent force constant, valid under certain conditions. Diffusion processes have attracted a great amount of scientific attention because of their presence in a wide range of phenomena. Brownian motion is the most widely known class of diffusion which is usually driven by thermal noise. However ,there are other classes of diffusion which cannot be classified as Brownian motion and therefore, fall under the category of Anomalous diffusion. As the name suggests, the properties of this class of diffusion are very different from those for usual Brownian motion. We are interested in a particular class of anomalous diffusion referred to as L´evy flights in which the step sizes taken by the particle during the random walk are obtained from what is known as a L´evy distribution. The diverging mean square displacement is a very typical feature for L´evy flights as opposed to a finite mean square displacement with a linear dependence on time in the case of Brownian motion. L´evy distributions are characterized by an index α where 0 <α ≤ 2. When α =2, the distribution becomes a Gaussian and when α=1, it reduces to a Cauchy/Lorentzian distribution. In the overdamped limit of friction, the probability density or the propagator associated with L´evy flights can be described by a position space fractional Fokker-Planck equation(FFPE)[1–3]. Jespersen et al. [4]have solved the FFPE in the Fourier domain to obtain the propagator for free L´evy flight(absence of an external potential) and L´evy flights in linear and harmonic potentials. We use a path integral technique to study L´evy flights. L´evy distributions rarely have a compact analytical expression in the position space. However, their Fourier transformations are rather simple and are given by e−D │p│α where D determines the width of the distribution. Due to the absence of a simple analytical expression, attempts in the past to study L´evy flights using path integrals in the position space [5, 6] have not been very successful. In our approach, we have tried to make use of the elegant representation of the L´evy distribution in the Fourier space and therefore, we write the propagator in terms of a two-dimensional path integral –one over paths in the position space(x)and the other over paths in the Fourier space(p). We shall refer to this space as the ‘phase space’. Such a representation is similar to the Hamiltonian path integral of quantum mechanics which was introduced by Garrod[7]. If we try to perform the path integral over Fourier variables first, then what remains is the usual position space path integral for L´evy flights which is rather difficult to solve. Instead, we perform the position space path integral first which results in expressions which are rather simple to handle. Using this approach, we have obtained the propagators for free L´evy flight and L´evy flights in linear and harmonic potentials in the over damped limit [8]. The results obtained by this method are in complete agreement with those obtained by Jesepersen et al. [4]. In addition to these results, we were also able to obtain the exact propagator for L´evy flights in a harmonic potential with a time-dependent force constant which has not been reported in the literature. Another interesting problem that we have considered in the over damped limit is to obtain the probability distribution for the area under the trajectory of a L´evy particle. The distributions, again, were obtained for free L´evy flight and for L´evy flights subjected to linear and harmonic potentials. In the harmonic potential, we have considered situations where the force constant is time-dependent as well as time-independent. Like in the case of the over damped limit, the probability distribution for L´evy flights in the under damped limit of friction can also be described using a fractional Fokker-Planck equation, although in the full phase space. However, this has not yet been solved for any general value of α to obtain the complete propagator in terms of both position and velocity. Using our path integral approach, the exact full phase space propagators have been obtained for all values of α for free L´evy flights as well as in the presence of linear and harmonic potentials[8]. The results that we obtain are all exact when the potential is at the most harmonic. If the potential is higher than harmonic, like the cubic potential, we have used a semi classical evaluation where, we extremize the action using an optimal path and further, account for fluctuations around this optimal path. Such potentials are very useful in describing the problem of escape of a particle over a barrier. The barrier crossing problem is very extensively studied for Brownian motion (Kramers problem) and the associated rate constant has been calculated in a variety of methods, including the path integral approach. We are interested in its L´evy analogue where we consider the escape of a particle driven by a L´evy noise over a barrier. On extremizing the action which depends both on phase space variables, we arrived at optimal paths in both the position space as well as the space of the conjugate variable, p. The paths form an infinite hierarchy of instant on paths, all of which have to be accounted for in order to obtain the correct rate constant. Care has to be taken while accounting for fluctuations around the optimal path since these fluctuations should be independent of the time-translational mode of the instant on paths. We arrived at an ‘orthogonalization’ scheme to perform the same. Our procedure is valid in the limit when the barrier height is large(or when the diffusion constant is very small), which would ensure that there is small but a steady flux of particles over the barrier even at very large times. Unlike the traditional Kramers rate expression, the rate constant for barrier crossing assisted by L´evy noise does not have an exponential dependence on the barrier height. The rate constant for wide range of α, other than for those very close to α = 2, are proportional to Dμ where, µ ≈ 1 and D is the diffusion constant. These observations are consistent with the simulation results obtained by Chechkin et al. [9]. In addition, our approach when applied to Brownian motion, gives the correct dependence on D. In equilibrium statistical mechanics we have considered two problems. In the first one, we have evaluated the imaginary time propagator for a harmonic oscillator with a time-dependent force constant(ω2(t))exactly, when ω2(t) is of the form λ2(t) - λ˙(t)where λ(t) is any arbitrary function of t. We have made use of Hamiltonian path integrals for this. The second problem that we considered was the evaluation of the partition function for hindered rotors. Hindered rotors are molecules which have a barrier for internal rotation. The molecule behaves like free rotor when the barrier is very small in comparison with the thermal energy, and when the barrier is very high compared to thermal energy, it behaves like a harmonic oscillator. Many methods have been developed in order to obtain the partition function for a hindered rotor. However, most of them are some what ad-hoc since they interpolate between free-rotor and the harmonic oscillator limits. We have obtained the approximate partition function by writing it as the trace of the density matrix and performing a harmonic approximation around each point of the potential[10]. The density matrix for a harmonic potential is in turn obtained from a path integral approach[11]. The results that we obtain using this method are very close to the exact results for the problem obtained numerically. Also, we have devised a proper method to take the indistinguishability of particles into account in internal rotation which becomes very crucial while calculating the partition function at low temperatures.

Un graphe arête-colorié Gc est un graphe dont les arêtes sont coloriées par un ensemble de couleurs données. Un sous-graphe de Gc est dit proprement colorié s'il ne contient pas d'arêtes adjacentes de même couleur. Un graphe ou multigraphe c-arête-colorié Gc, est dit k-lié (respectivement k-arête-lié) si et seulement si quelque soient 2k sommets distincts de V(Gc), notés, x1 y1 , x2 y2 , ..., xk yk , il existe k chaînes élémentaires sommet-disjointes (respectivement arête-disjointes) proprement arête-coloriées, reliant x1 à y1 , x2 à y2 , ... , xk à yk .Un arbre couvrant propre d'un graphe Gc est un sous-graphe de Gc qui est un arbre couvrant proprement colorié.Un arbre couvrant faiblement colorié est une arborescence telle qu'il existe une chaîne proprement coloriée entre la racine et chaque sommet du graphe.Dans la première partie de cette thèse, nous donnons des conditions suffisantes pour qu'un graphe arête-colorié soit k-lié. C'est un problème classique en théorie des graphes, avec des applications multiples. Ainsi, nous avons établi entre autres les résultats suivants.A) Tout multigraphe 2-arête-colorié d'ordre n ≥ 242k tel que dc(Gc) ≥ n/2+k –1, est k-lié. B) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k et de taille m≥ cn(n–1)/2 – c(n–2k +1)+1 est k-lié.C) Tout multigraphe c-arête-colorié d'ordre n ≥ 2k tel que dc(x) ≥ n/2 pour tout sommet x, est k-arête-lié.D) Tout multigraphe 2-arête-colorié d'ordre n ≥ 2k ≥ 10 et de taille m ≥ n2 –5n + 11 tel que dc(x) ≥ 1 pour tout sommet x, est k-arête-lié.Dans la seconde partie de cette thèse, deux autres problèmes classiques en théorie des graphes sont traités dans la version arête-coloriée. Il s'agit des arbres couvrants et des chaînes hamiltoniennes. Nous donnons ci-dessous quelques résultats.E) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, a un arbre couvrant propre.F) Tout graphe Gc connexe c-arête-colorié de degré rainbow rd(Gc)=k et d'ordre n ≥ C²k+1 + k + 2 avec c ≥ C²n–k–1 + k +1, possède un arbre couvrant propre.G) Tout graphe simple c-arête-colorié k-connexe d'ordre n ≥ ((k + j)2 + 3(k + j) – 2)/2 avec c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , où j(j –1)=k , possède un arbre couvrant faiblement colorié.H) Tout multigraphe Gc d'ordre n ≥ 14 et de taille m ≥ (n – 3)(n – 4) + 3n – 2 tel que rd(Gc) = 2, possède une chaîne hamiltonienne propre. I) Tout multigraphe c-arête-colorié d'ordre n ≠ 5, 7 et de taille m ≥ n2 – 3n + 4, possède une chaîne hamiltonienne propre.La plupart des résultats exposés, sont les meilleurs possibles relativement aux propriétés sur les conditions suffisantes. / A c-edge-colored graph Gc is a graph whose edges are colored by a given set of colors. A subgraph of Gc is proper if no two adjacent edges have the same color.A c-edge-colored graph or multigraph Gc is k-linked (respectively k-edge-linked) if for any 2k distinct vertices, say x1 y1 , x2 y2 , ..., xk yk , there exist k vertex-disjoint (respectively edge-disjoint) proper paths joining x1 to y1 , x2 to y2 , ... , xk to yk .A proper spanning tree of a graph Gc is a spanning tree such that any two adjacent edges differ in colors.A weak spanning tree is a spanning rooted tree such that there exists a proper path between the root and every vertex of the graph.In the first part of this thesis, we provide conditions which are sufficient for an edge-colored graph to be k-linked. It is a classic problem in graph theory , with many applications. So, we established among others the following results.A) Every 2-edge-colored multigraph of order n ≥ 242k such that dc(Gc) ≥ n/2+k –1, is k-linked.B) Every c-edge-colored multigraph of order n ≥ 2k and size m≥ cn(n–1)/2 – c(n–2k +1)+1 is k-linked.C) Every c-edge-colored multigraph of order n ≥ 2k is k-edge-linked if for each vertex x, dc(x) ≥ n/2.D) Every 2-edge-colored multigraph of order n ≥ 2k ≥ 10 and size m ≥ n2 – 5n + 11 is k-edge-linked if for each vertex x, dc(x) ≥ 1.In the second part of this thesis, two other classic problems in graph theory are treated in edge-colored version: spanning trees and hamiltonian paths. We give below some results.E) Every c-edge-colored simple k-connected graph of order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree.F) Every c-edge-colored connected graph Gc of rainbow degree rd(Gc)=k and order n ≥ C²k+1 + k + 2 with c ≥ C²n–k–1 + k +1, has a proper spanning tree. G) Every c-edge-colored simple k-connected graph of order n ≥ ((k + j)2 + 3(k + j) – 2)/2 and c ≥ ((n – k – j)(n – k – j – 1))/2 + 2 , with j(j –1)=k , has a weak spanning tree.H) Every c-edge-colored multigraph Gc of order n ≥ 14 and size m ≥ (n – 3)(n – 4) + 3n – 2 such that rd(Gc) = 2, has a proper hamiltonian path.I) Every c-edge-colored multigraph of order n ≠ 5, 7 and size m ≥ n2 – 3n + 4, has a proper hamiltonian path.Most of the given results are the best possible with regard to the properties on the sufficient conditions.