PhD Theses (Mathematics)

Browse

Now showing 1 - 20 of 123

(A) Posteriori error Analysis of Finite Element Method for Parabolic Interface Problems
(2015) Gupta, Jhuma Sen
The Primary aim of the thesis is to study a posteriori error analysis of parabolic interface problems in a bounded convex polygonal domain in R2...
(A) Posteriori Error Analysis of Finite Element methods for Parabolic Integro-differential Equations
(2014) Reddy, G. Murali Mohan
The aim of the thesis is to study a posteriori error analysis of finite element method for linear parabolic integro-differential equations (PIDEs) in a convex polygonal or polyhedral domain. PIDEs and their variants arise in various applications, such as heat conduction in material with memory, the compression of poro-viscoelasticity media, nuclear reactor dynamics and the epidemic phenomena in biology. Since PIDE may be thought of as a perturbation of the purely parabolic problem, it is therefore, natural to expect how the a posteriori error analysis of parabolic problems can be extended to PIDEs. Such an extension is not straightforward in the presence of Volterra integral term. In isotropic settings, we derive a posteriori error estimators for both the spatially semidis- crete and the fully discrete (backward Euler and Crank-Nicolson) schemes for PIDEs. A novel space-time reconstruction operator is introduced which is an a posteriori counterpart of the Ritz-Volterra projection. Moreover, this reconstruction operator is a generalization of the elliptic reconstruction operator and we call it as Ritz-Volterra reconstruction operator. The Ritz-Volterra reconstruction operator is used in a crucial way to derive optimal order a pos- teriori error estimates in the L1(L2)-norm. The related a posteriori error estimates for the Ritz-Volterra reconstruction error are also established. For the Crank-Nicolson scheme, the derivation of the a posteriori error estimator relies essentially on the Ritz-Volterra reconstruc- tion operator and a novel space-time quadratic (in time) reconstruction operator. To reduce the number of degrees of freedom and computational effort to achieve the same convergence as compared to the isotropic meshes, we also consider the a posteriori error anal- ysis for PIDE in an anisotropic framework. We derive a posteriori error estimators for both fully discrete backward Euler and Crank-Nicolson schemes for PIDEs in the L2(H1)-norm in a two dimensional convex polygonal domain. The a posteriori error indicators corresponding to space discretizations are derived using the anisotropic interpolation estimates in conjunc- tion with a Zienkiewicz-Zhu error estimator to approach the error gradient. The error due to time discretization is derived using continuous, piece wise linear polynomial in time in case of backward Euler scheme, whereas to recover optimality for Crank-Nicolson scheme we intro- duce continuous, piecewise quadratic time reconstructions, namely, Crank-Nicolson memory reconstruction and three point reconstruction.
(A) Posteriori Error Estimates for Finite Element Discretizations of Parabolic Optimal Control Problems
(2022) Manohar, Ram
The main objective of this thesis is to derive a posteriori error estimates for nite element discretizations of optimal control problems governed by parabolic partial di erential equations. Both distributed and boundary parabolic optimal control problems are considered and analyzed. We first study L1(0; T;L2())􀀀a posteriori error analysis for parabolic optimal control problem (POCP) with distributed control. To discretize the state and co-state variables we use the piecewise linear and continuous nite elements, while the piecewise constant functions are used to discretize the control variable. The backward Euler scheme is applied for the time discretization. An elliptic reconstruction technique in conjunction with energy argument is used to derive a posteriori error estimates for the state and costate variables in the L1(0; T;L2( ))- norm. The rst-order necessary optimality condition is used to derive the error estimate for the control variable in the L1(0; T;L2( ))-norm. The second problem considers the POCP with distributed control and discusses a posteriori error analysis for both semi-discrete and fully discrete nite element method. The variational discretization is used to approximate the state and co-state variables with the piecewise linear and continuous functions, while the control variable is computed by using the implicit relation between the control and co-state variables. The temporal discretization is based on the backward Euler method. The key feature of this approach is not to discretize the control variable but to implicitly utilize the optimality conditions for the discretization of the control variable. We use the elliptic reconstruction technique in conjunction with heat kernel estimates for linear parabolic problem to derive a posteriori error estimates for the state, co-state and control variables in the L1(0; T; L1( ))-norm. Use of elliptic reconstruction technique greatly simpli es the analysis by allowing us to take the advantage of existing elliptic maximum norm error estimates and the heat kernel estimate. Our next problem focuses on nite element approximations of the POCP with controls acting on a lower dimensional manifold. The manifold considered here is either a point, or a curve or a surface which is lying completely in the space domain. In addition, the manifold is assumed to be either time independent or evolved with the time. The state and co-state variables are approximated by the piecewise linear and continuous nite elements whereas the piecewise constant functions are employed to approximate the control variable. Moreover, the discrete-in-time scheme is based on the backward Euler method. We derive a posteriori error estimates for the various dimensions of the manifold. We next turn our attention to study local a posteriori error estimates for the space-time nite element approximations of parabolic boundary control problem (PBCP). In many engineering applications, it is often useful to study the behavior of the state and co-state variables in a small neighborhood of the boundary. Therefore, a posteriori error estimators in some suitable local norms have become more useful, and the derivation of these estimates is not straightforward. Therefore, an attempt has been made in this thesis to derive local a pos- teriori error estimates for the PBCP. The space-time discretization is accomplished by using the piecewise linear and continuous nite element approximations for the state and co-state variables while the piecewise constant function spaces employed for the control variable. We use the backward Euler method to approximate the time derivative. We derive three di erent reliable local a posteriori error estimates for Neumann boundary control problems with the observations of the boundary state, the distributed state and the nal state. Our derived estimators are of local character in the sense that the leading terms of the estimators depend on the small neighborhood of the boundary. These new local a posteriori error bounds can be used to study the behaviour of the state and co-state variables around the boundary and provide the necessary feedback in terms of the error indicators for the adaptive mesh re nements in the nite element method. Our last problem is devoted to study nite element approximation for nonlinear PBCP. The error analysis is carried out by using the piecewise linear and continuous nite elements for the approximation of the state and co-state variables whereas the approximation of the control variable is done with the piecewise constant functions. The backward Euler method is used to approximate the time derivative. The reliable type local a posteriori error bounds for the state, co-state and control variables in the L2(0; T;L2(􀀀))- norm are derived, while the a posteriori error estimates for the control variable is established by assuming the second-order optimality condition. Computational results are presented to illustrate the performance of the derived estimators.
(A) Priori error analysis for the finite element approximations to various interface problems arising in biological media
(2021) Dutta, Jogen
The main objective of this thesis is to study a priori error analysis of finite element Galerkin methods for some interface problems arising in biological media. Interface problems are often referred to as differential equations with discontinuous coeffcients. The discontinuity of the physical coeffcients is due to the presence of different material properties across the interface. In biological system it is natural to have heterogeneity in the underlying medium as properties of biological media vary between different layers. Due to the presence of discontinuous coeffcients across the interface, interface problems usually lead to non-smooth solutions. Owing toits mathematical complexity and low regularity of its solutions, the study of interface problems has remained a major part of the mathematical study up to the present day. In this thesis we attempt to study the a priori error analysis of some of the interface problems arising in biological media using fitted finite element method. In our first problem, we analyze finite element Galerkin methods applied to pulsed electric model arising in biological tissue when a biological cell is exposed to an electric field. Considering the cell to be a conductive body, embedded in a more or less conductive medium, the governing system involves an electric interface (surface membrane), and heterogeneous permittivity and a heterogeneous conductivity. A tted finite element method with straight interface triangles is proposed to approximate the voltage of the pulsed electric model across the physical media. Optimal pointwise-in-time error estimates in L2-norm and H1-norm are shown to hold for semidiscrete scheme even if the regularity of the solution is low on the whole domain. Further, a fully discrete nite element approximation based on Crank-Nicolson scheme is analyzed and related optimal error estimates are derived. Finally, we give numerical examples to verify the theoretical results. We next proceed to the a priori error analysis of non-Fourier bio heat transfer model in multi-layered media. Specifically, we employ the Maxwell-Cattaneo equation on the physical media with discontinuous coe cients. A fitted finite element method is proposed and analyzed for a hyperbolic heat conduction model with discontinuous coefficients. Typical semidiscrete and fully discrete schemes are presented for a fitted finite element discretization with straight interface triangles. The fully discrete space-time finite element discretizations is based on second order in time Newmark scheme. Optimal a priori error estimates for both semidiscrete and fully discrete schemes are proved in L1(L2) norm. Numerical experiments are reported for several test cases to confirm our theoretical convergence rate. Finite element algorithm presented here can be used to solve a wide variety of hyperbolic heat conduction models for non-homogeneous inner structures. Finally, we have extended our analysis to study the dual-phase-lag(DPL) bio heat model in heterogeneous medium. Well-posedness of the model interface problem and a priori estimates of its solutions are established. A new non-standard elliptic type projection operator is introduced to derive optimal convergence result for the semidiscrete solution in L1(L2) norm. The fully discrete space-time finite element discretizations is based on second order in time Newmark scheme. Optimal a priori error estimate for the fully discrete scheme is proved in L1(L2) norm. Finally, numerical results for two dimensional test problems are presented in support of our theoretical findings. Finite element algorithm presented here can contribute to a variety of engineering and medical applications.
(A) Study of Class Number of Real Quadratic and Cubic Fields
(2016) Chakraborty, Debopam
The primary goal of the thesis is to study class number of the ring of integers of a number field and related arithmetical properties. The first part of the thesis provides a solution to a classical problem posed by Dirichlet. Dirichlet asked whether exist infinitely many real quadratic fields with 1 as relative class number. It has been shown in the thesis that a real quadratic field will always have 1 as relative class number for the conductor 3, depending om certain conditions on the field . The thesis also provides a necessary and sufficient condition for a real quadratic field to have relative class number 1. Moreover, the thesis contains significant generalization of the continued fraction approach of A. Furness and E. A. Parker towards relative class number. Using this approach, the thesis also shows the existence of another infinite family of real quadratic fields with relative class number 1 with an odd prime dividing the discriminant as conductor.
(A) Study of Some Parameters in Signed Graphs
(2022) Deepak
Graphs with positive or negative edges are called signed graphs. We denote a signed graph Σ by (G, ϕ), where G is called the underlying graph of Σ and ϕ is a function that assigns +1 or −1 to the edges of G. The set of negative edges in Σ is known as the signature of Σ. An unsigned graph can be realized as a signed graph in which all edges are positive. Switching Σ by a vertex v is to change the sign of each edge incident to v. Switching is a way of turning one signed graph into another. Two signed graphs are called switching equivalent if one can be obtained from the other by a sequence of switchings. Further, two signed graphs are said to be switching isomorphic to each other if one is isomorphic to a switching of the other. In Chapter 2 of the thesis, we classify the switching non-isomorphic signed graphs arising from K6, P3,1, P5,1, P7,1, and B(m, n) for m ≥ 3, n ≥ 1, where K6 is the complete graph on six vertices, Pn,k denotes the generalized Petersen graph and B(m, n) denotes the book graph consisting of n copies of the cycle Cmwith exactly one common edge. We also count the switching non-isomorphic signatures of size two in P2n+1,1 for n ≥ 1. We prove that the size of a minimum signature of P2n+1,1, up to switching, is at most n + 1.
(A) Study of torsion of elliptic curves and fundamental units over number fields
(2018) Sarma, Naba Kanta
The primary objective of the thesis titled “A Study of Torsion of Elliptic Curves and Fundamental Units over Number Fields” is to study the torsion subgroup of elliptic curves over certain quadratic number fields and to establish certain congruence relations for the fundamental unit of totally imaginary biquadratic number fields of odd class number. The first part of the work is devoted to finding possible torsion structures over given quadratic fields. In 1922, Louis Mordell proved that the group of rational points of an elliptic curve over the rational field is finitely generated and in 1928, Andreَ Weil generalized this result for abelian varieties over algebraic number fields. In 1977, Barry Mazur opened up a vast area of research by listing all possible torsion subgroups of all possible elliptic curves over the rational field. He showed that only 15 possible groups could occur as the torsion subgroup of elliptic curves over Q. After extensive collaborations among various mathematicians, Kenku, Momose and Kamienny to name a few, a complete list of 26 groups was finally published for the torsion subgroup of elliptic curves over all possible quadratic number fields.In 2011, Najman computed the torsion subgroups of all elliptic curves over the imaginary quadratic fields Q (√-1) and Q (√-3) separately. In 2012, Kamienny and Najman outlined a method to study the possible torsion structure over a given quadratic field. We follow their method in determining the possible torsion structures over the remaining imaginary quadratic fields of class number 1. We also compute the possible torsion structures over the real quadratic fields Q(√2) and Q(√5), which have the smallest discriminants among all real quadratic fields Q(√d) with d ≡2,3 (mod 4 ) and d ≡1( mod 4 ) respectively.In the latter half of our work, we prove certain congruence relations for the fundamental unit of totally imaginary biquadratic fields of odd class number. In 2014, Zhang and Yue obtained certain congruence relations for the fundamental unit of real quadratic fields of odd class number by using 2-adic analysis. In 2016, Chakraborty and Saikia obtained the same congruences by elementary methods. In this work, we refine these congruences by using ramification of primes in quadratic fields. We then use these congruences to establish certain congruence relations for the fundamental unit of totally imaginary biquadratic fields of odd class number.
(A) Study on fractal interpolation in shape preserving and in numerical methods for ordinary differential equations
(2019) Balasubramani, N
Interpolation is an essential tool to approximate the unknown function from its samples. Many situations, when data arises from various complex phenomena, the data exhibits irregularity. Giving smooth approximation for these data may not be suitable. Fractal interpolation provides a non-smooth approximation for the interpolation data. Iterated function system is a basic tool to construct the fractal interpolation function and the graph of the fractal interpolation function is the attractor of the iterated function system. Data visualization is an essential subject because when data comes from scientific experiments or natural phenomena, the data may contains certain shape properties and preserving the shapes of these data are needed. Though traditional interpolation methods (polynomial, spline etc.) are good for shape preserving, these methods may not be good for irregular representation of the unknown functions. Fractal interpolation functions can be used both in shape preserving and irregular representation of the unknown functions. Also, fractal interpolation can be used to develop the numerical methods for the boundary-value problems of the ordinary differential equations. In this thesis, we have developed rational cubic fractal interpolation functions for preserving the shapes of the univariate data. We have constructed fractal interpolation surface for preserving the shapes of the bivariate data. With the help of fractal cubic spline, we have developed the numerical schemes for singularly perturbed boundary-value problems and singular boundary-value problems. Using non-polynomial fractal cubic spline, we have developed numerical schemes for singularly perturbed boundary-value problems. With the help of fractal quintic spline, we proposed the numerical schemes for singularly perturbed boundary-value problems, nonlinear boundary-value problems and fourth-order boundary-value problems.
(A) Study on some classes of fractional differential equations with non-instantaneous impulses
(2019) Borah, Jayanta
Study of dynamical systems with discontinuous trajectories or with impulse effect, is one of the most exciting subjects due to its extensive applications in realistic mathematical modeling of a wide variety of practical situations. Fractional differential equations which already have the hereditary property, with impulse effect, will give better results and the study of the corresponding theory is a hugely demanding task. This thesis is devoted to the study of the existence and uniqueness of mild solutions of some classes fractional evolution equations subject to non-instantaneous impulses.
Adaptive Finite Element Methods for Parabolic Interface Problems
(2021) Ray, Tanushree
The main objective of this thesis is to study adaptive nite element methods (AFEMs) for parabolic interface problems in a bounded convex polygonal domain in R2. Interface problems arise in a wide variety of applications in science and engineering such as material sciences and fluid dynamics when two or more distinct materials or fluids with different conductivities or densities or diffusion are interacting across the interface. Due to the discontinuity of the coefficients along the interface, the analytic solutions are rarely available for the interface problems. Therefore, the numerical approximation is the only way to proceed with such problems. Even if the solution is smooth in each individual subdomain, the global regularity of the solution of such problem is very low. As a result, it is very challenging to achieve higher order accuracy in the nite element method (FEM). Therefore, much attention has been paid in the recent years to the study both theory and numerics of time-dependent interface problems. It is known that AFEMs are widely used numerical techniques to enhance the accuracy and effciency of the nite element method. The key to the success of AFEMs relies on the a posteriori error analysis, which provides error indicators for the design of adaptive algorithms. The adaptive method reduces the computational efforts and ensures higher density nodes in a particular area of the given domain where the solution is very diffcult to approximate.
Affine Near-Semirings over Brandt Semigroups
(2014) Kumar, Jitender
The thesis aims at studying various structural properties of affine near-semirings over Brandt semigroups. The study considers various aspects, viz. semigroup theoretic properties, ring theoretic properties and formal language theoretic connections. At the outset, the thesis classifies the elements of an affine near-semiring over Brandt semigroup, denoted by A+(Bn), and finds the cardinality of A+(Bn), for an arbitrary natural number n. In order to ascertain the semigroup theoretic properties of A+(Bn), the thesis completely characterizes the Green relations on both of its semigroup reducts. The thesis reveals that the additive semigroup reduct is eventually regular and the multiplicative semigroup reduct is orthodox. Further, the rank properties of these semigroup reducts are investigated in detail. By determining all right ideals, ideals and radicals, the thesis studies the ring theoretic structure of A+(Bn). The study establishes certain formal language theoretic connections to A+(Bn) by showing that both of its semigroup reducts are syntactic semigroups.
Algorithms for Geometric Covering Problems
(2016) Manjanna, B
Motivated by the applications in facility location, VLSI design, image processing and motion planning, geometric covering problems have been studied extensively in the literature. In this thesis various geometric covering problems such as covering points with disks, and squares, covering rectangular regions and convex polygonal regions with disks are considered. The problems are investigated by proposing approximation, parameterized and heuristic algorithms. The Discrete Unit Disk Cover (DUDC) problem is one of the well known geometric covering problems. The DUDC problem is a NP-complete problem.
Analysis of robust computational techniques for singularly perturbed system of parabolic partial differential equations
(2018) Singh, Maneesh Kumar
In this thesis, our primary interest is to provide some uniformly convergent computational techniques for solving singularly perturbed system of parabolic initial-boundary-value problems (IBVPs) of convection-diffusion and reaction-diffusion types with boundary and interior layers in one- and two-dimensions. These kinds of problems are identified by system of partial differential equations in which the highest order spatial derivatives are multiplied by small parameters, known as singular perturbation parameters. The solution of such kind of problems exhibits boundary or/and interior layers where the solution varies rapidly, while away from these layers the solution behaves smoothly. Due to appearance of the layer phenomena, it is an interesting task to develop parameter-uniform numerical methods. The purpose of this thesis is to apply and analyze parameter-uniform fitted mesh methods (FMMs) for solving singularly perturbed system of parabolic PDEs in one- and two-dimensions.We begin this thesis with an introduction followed by a section describing the objectives and the motivation for solving singularly perturbed system of parabolic PDEs. Then, we discuss preliminaries which are used throughout the thesis. Next, we move forward to the main work of the thesis. First, we analyze a uniformly convergent numerical scheme for system of 1D parabolic convection-diffusion IBVPs exhibiting overlapping boundary layers. Then, to improve the accuracy of the proposed numerical scheme, a post-processing technique is discussed. The hybrid difference numerical scheme is proposed for system of 1D parabolic PDE on the piecewise-uniform Shishkin mesh. Later, we have considered uniformly convergent upwind based numerical scheme for singularly perturbed system of 1D parabolic convection-diffusion problems with overlapping interior layers. Then we discuss singularly perturbed system of 2D parabolic convection-diffusion and reaction-diffusion problems. First, we analyze a fractional-step method to discretize the time-derivative of the singularly perturbed system of 2D convection-diffusion PDEs. The resulting one-dimensional equations are solved by using the classical upwind scheme. Next, we consider singularly perturbed system of two-dimensional reaction-diffusion problems with one parameter. Here, we discretize the time-derivative by the fraction-step method and spatial derivatives by the central difference scheme for the reduced stationary problem. At the end, we have considered system of 2D reaction-diffusion problem containing different diffusion parameters. The spatial derivatives are discretized by the central difference scheme on piecewise-uniform Shishkin mesh. Then, the time derivative is discretized by implicit-Euler scheme on uniform mesh in the resulting problem. Numerical results are produced to validate the theoretical error estimates. Finally, we summarize the results obtained in this thesis. At the end of this thesis, possible future works are discussed based on the work carried out in this thesis.
Analytical Study on Solute Transportation in Streams with Transient Storage and Hyporheic Zones
(2009) Kumar, Akhilesh
This thesis presents the derivation of general analytical solutions of the transient stor- age model and also of the diDusive transfer model for the longitudinal solute transport in streams with transient storage and hyporheic zones for conservative and reactive solutes. These general analytical solutions are derived by means of Laplace trans- form. The transient storage model deals with the Drst order mass transfer between the main channel of stream and the storage zone, and the diDusive transfer model deals with the diDusive mass transfer of solute between the main channel of stream and the hyporheic zone. Parameters of the transient storage model and also of the diDusive transfer model are estimated for the Uvas Creek tracer experiment by using the large scale Newton reDexive method. The analytical results of these models for conservative solutes are compared with the observed data of the Uvas Creek tracer experiment for chloride concentration. Sensitivity analysis is performed in order to identify the critical parameters on solute concentrations. EDects of diDerent param- eters that represent physical, chemical and hydrological processes involved in the transport of solutes in streams are studied for hypothetical situations. Results are presented for conservative solutes considering step concentration-time proDle as the upstream boundary condition whereas in the case of reactive solutes, an instantaneous release of the solute is considered to be the upstream boundary condition..
Appell series over finite fields and Gaussian hypergeometric series
(2021) Tripathi, Mohit
In this thesis we study classical hypergeometric series and Appell series over finite fields, and find finite field analogues of several product and summation formulas satisfied by the classical hypergeometric series. Hypergeometric functions over finite fields are known as Gaussian hypergeometric series. As an application of the product and summation formulas, we deduce several special vlaues of 2F1, 3F2 and 4F3-Gaussian hypergeometric series. Some of our special values of Gaussian hypergeometric series are evaluated at general arguments of the parameters. Recently, finite field alanogues of Appell series F1, F2 and F3 are introduced and their relations with certain Gaussian hypergeometric series are established. Integral representations of F1, F2 and F3 are used while defining their finite field analogues. However, integral representations of F4 are more complicated than the integral representations of F1, F2 and F3. Therefore, it is not straightforward to find an appropriate finite field analogue of F4 using its integral representations. To overcome this problem, we define finite field analogues of classical Appell series F1, F2 and F3 using purely Gauss sums, and this allows us to define a finite field analogue of the Appell series F4. We then establish finite field analogues of classical identities satisfied by the Appell series and hypergeometric series. As applications, we find several transformation formulas satisfied by the Gaussian hypergeometric series. For example, we express a 4F3-Gaussian hypergeometric series as a sum of Mo 2F1-Gaussian hypergeometric series. We also express 4F3-Gaussian hypergeometric series as a product of two 2F1-Gaussian hypergeometric series. Product formulas for Gaussian hypergeometric series have many significant applications. We find finite field analogues of certain product formulas satistied by the classical hypergeometric series. We express product of two 2F1-Gaussian hypergeometric series as 4F3- and 3F2-Gaussian hypergeometric series. We use properties of Gauss and Jacobi sums and our works on finite field Appell series to deduce these product formulas satisfied by the Gaussian hypergeometric series. We then use these transformations to evaluate explicitly some special values of 4F3- and 3F2-Gaussian hypergeometric series. By counting points on CM elliptic curves over finite fields, Ono found certain special values of 2F1- and 3F2-Gaussian hypergeometric series containing trivial and quadratic characters as parameters. Later, Evans and Greene found special values of certain 3F2-Gaussian hypergeometric series containing arbitrary characters as parameters from where some of the values obtained by Ono follow as special cases. We show that some of the results of Evans and Greene follow from our product formulas including a finite field analogue of the classical Clausen’s identity
Approximation algorithms for dominating set and its variants on unit disk graphs
(2018) Jallu, Ramesh Kumar
Dominating set and its variants have been studied extensively in the literature and are of broad and current research interest to many researchers due to its wide range of applications, including, but not limited to, networks, VLSI, clustering, map labeling and coding theory. In this thesis, minimum dominating set problem and some of its variants, such as minimum connected dominating set, minimum lair s dominating set, and maximum (weighted) independent set problems are studied on unit disk graphs. All the aforementioned problems are NP-hard on unit disk graphs. The high time complexity of the existing polynomial-time constant factor approximation algorithms motivated us to study these problems and design faster approximation algorithms and approximation schemes. The approximation algorithms and approximation schemes presented in this thesis outperform the existing algorithms in the literature in terms of time complexity. We introduced the liar s dominating set problem in the geometric setting. We showed that the problem is NP-hard even for unit disk graphs and designed constant factor approximation algorithms and an approximation scheme for the problem.
Approximation Algorithms for Facility Location Prob- lems in Graphs
(2021) Jena, Sangram Kishor
Dominating set and its variants have been studied extensively in the literature and are of broad and current research interest to many researchers due to its wide range of applications, including, but not limited to, networks, VLSI, clustering, map labeling, coding theory, etc. In this thesis, minimum dominating set problem and some of its variants, such as maximum distance-d independent set, minimum distance- d dominating set, minimum d-distance m-tuple (`; r)-dominating set, minimum vertex-edge dominating set, and minimum total dominating set problems are studied. All the aforementioned problems are NP-hard and none of them admit constant factor approximation algorithms for general graphs, unless P = NP. This motivated us to study the problems for special graph classes. We are the rst to de ne the d-distance m-tuple (`; r)-dominating set problem in general graphs, which is a collection of problems depending on the values of d; m; `, and r and all the other four problems are studied in unit disk graphs (UDGs) with known disk position for designing simple constant factor approximation algorithms with low time complexity and polynomial-time approximation schemes that outperform the existing results in the literature. Firstly, we study the geometric maximum distance-d independent set (GMDdIS) problem, for an integer d 3. We show that the decision version of the GMDdIS problem (for d 3) is NP-complete in unit disk graphs. Next, we propose a simple 4-factor approximation algorithm for GMDdIS problem in d2nO(d) time. Finally, we propose a PTAS for this problem of size at least 1(1+ 1k )2 jOPTj in k2nO(k) time, where jOPTj is the maximum cardinality of a GMDdIS. Secondly, we study the geometric minimum distance-d dominating set (GMDdDS) problem in unit disk graphs. We show that the decision version of the GMDdDS problem (for d 2) is NP-complete in unit disk graphs. We propose a simple 4-factor approximation algorithm for GMDdDS problem in d2nO(d) time, and a PTAS for this problem of size at most (1+ 1k )2 jOPTj in k2nO(k) time, where OPT is the minimum cardinality of a GMDdDS. Next, we study the minimum d-distance m-tuple (`; r)-dominating set ((d; m; `; r) set) problem in general graphs. In this problem, we prove that the problem of deciding whether a graph G has a 1-distance m-tuple (`; r)-dominating set for each xed value of m; `, and r of cardinality at most k is NP-complete for gen- eral graphs. Next, we prove that the problem of deciding whether a graph G has a d-distance m-tuple (`; 2)-dominating set for each xed value of d(> 1);m, and ` of cardinality at most k is NP-complete. We also prove that for any " > 0, the 1-distance m-tuple (`; r)-domination problem and the d-distance m-tuple (`; 2)- domination problem cannot be approximated within a factor of ( 12 􀀀 ") ln jV j and ( 1/4 􀀀 ") ln jV j, respectively, unless P = NP. Next, we introduce a variant of dominating set problem in UDGs and we call this problem as the geometric minimum vertex-edge dominating set (GMVEDS) problem. Simply, a vertex pi 2 V , vertex-edge dominates every edge pipj , as well as every edge adjacent to these edges. We prove that the problem GMVEDS belongs to the NP-hard class in unit disk graphs. We propose a simple 4-factor approximation algorithm in polynomial time. We also designe a PTAS for this problem, which runs in O(nc) time, where c = O( 1 log 1 ). Finally, we study the geometric minimum total dominating set (GMTDS) problem in UDGs. In the GMTDS problem, we prove that the decision version of the TDS problem in the unit disk graph is NP-complete. Next, we propose a simple 8-factor approximation algorithm in O(n log k) time, where n is the input size and k is the output size of the algorithm. We also propose a PTAS for this problem of size at most (1 + 1k )2 jOPTj in O(k2n2(d2 p 2ke)2) time, where OPT is the optimum solution.
Approximation Algorithms for Sweep Coverage in Wireless Sensor Networks
(2015) Gorain, Barun
Coverage is one of the most important issues in wireless sensor networks (WSNs) and it is a well studied research area. To ensure coverage, a set of sensors continuously monitor the subject to be covered. Sweep coverage is a recent development for the applications of WSNs where periodic monitoring by a set of mobile sensors is sufficient instead of continuous one like traditional coverage. In this thesis, we remark on the flaw of the approximation algorithms (Mo Li, Wei-Fang Cheng, Kebin Liu, Yunhao Liu, Xiang-Yang Li, and Xiangke Liao, Sweep coverage with mobile sensors, IEEE Trans. Mob. Comput., 10(11):15341545, 2011.) for sweep coverage for a set of points. We propose a 3-approximation algorithm to guarantee sweep coverage for the vertices of a weighted graph, where vertices are considered as the set of points. When vertices of the graph have different sweep periods and processing times, we propose a O(log )-approximation algorithm as a solution, where is the ratio of the maximum and minimum sweep periods among the vertices. If speeds of the mobile sensors are different, we prove that it is impossible to design any constant factor approximation algorithm to solve the problem unless P=NP. Energy is an important issue for the sensors. To incorporate it, an energy efficient sweep coverage problem is proposed, where a combination of static and mobile sensors are used. The problem is NPhard and cannot be approximated within a factor of 2 unless P=NP. An 8-approximation algorithm is proposed to solve it. A 2-approximation algorithm is also proposed for a special case of the problem, which is the best possible approximation factor. Energy utilization for the mobile sensors is restricted as they are battery-powered. Considering the limitation, an energy restricted sweep coverage problem is defined and a (5 + 2 )-approximation algorithm is proposed to solve this NP-hard problem. Periodic patrol inspection is important to detect illegal movement across national border. A portion of border can be modeled as a finite length curve. With this model, we introduce barrier sweep coverage concept for periodic monitoring of finite length curves in two dimensional plane. A solution is proposed to sweep cover a finite length curve with optimal number of mobile sensors. An energy restricted barrier sweep coverage problem is introduced and proposed a 13 3 -approximation algorithm for a finite length curve. We prove that finding minimum number of mobile sensors to sweep coverage for a set of finite length curves is NP-hard and cannot be approximated within a factor of 2. For that a 5-approximation algorithm is proposed. A 2-approximation algorithm is also proposed to solve the problem for a special case, where each mobile sensor must visit all points of each curve. We formulate a data gathering problem by a set of data mules and prove that the problem is NP-hard. A 3-approximation algorithm is proposed to solve it. Through simulation, performance of the algorithm for multiple finite length curves is investigated. We introduce area sweep coverage problem and prove that the problem is NP-hard. A 2 p 2-approximation algorithm is proposed to solve the problem for a square region. For arbitrary bounder region A the approximation factor is 2 (p 2 + 2rP Area(A).
Arithmetic properties of certain partition functions and modular forms
(2019) Ray, Chiranjit
This thesis studies arithmetic properties of `-regular overpartitions, Andrews' singular overpartitions, overpartitions into odd parts, cubic and overcubic partition pairs, and Andrews' integer partitions with even parts below odd parts. We use various dissections of Ramanujan's theta functions to nd in nite families of arithmetic identities and Ramanujan-type congruences for `-regular overpartitions and overpartitions into odd parts. We nd certain congruences satis ed by A`(n) for ` = 4; 8 and 9, where A`(n) denotes the number of `-regular overpartitions of n. We nd several in nite families of congruences including some Ramanujan-type congruences satis ed by A2`(n) and A4`(n) for any ` 1. We next prove several congruences for po(n) modulo 8 and 16, where po(n) denotes the number of overpartitions of n into odd parts. We also obtain the generating functions for po(16n+2), po(16n+6), and po(16n + 10); and some new p-dissection formulas.
Backward Perturbation and Sensitivity analysis of Structured polynomial Eigenomial Eigenvalue Problem
(2008) Adhikari, Bibhas
The main theme of the thesis is structured perturbation and sensitivity analysis of structured polynomial eigenvalue problem. Structured mapping problem naturally arises when analyzing structured backward per- turbation of structured eigenvalue problem. Given two matrices X and B of same size, the structured mapping problem requires to Dnd a \structured"" matrix A; if any, having the small- est norm such that AX = B: We provide a complete solution of structured mapping problem. More generally, we provide a complete solution of the structured inverse least-squared problem (SILSP): min A kAX D BkF ; where the minimum is taken over \structured"" matrices. As a consequence of structured map- ping problem, we determine structured backward errors of approximate invariant subspaces of structured matrices. We also analyze structured pseudospectra of structured matrices. Next, we undertake a detailed structured backward perturbation analysis of structured ma- trix polynomials and derive explicit computable expressions for structured backward errors of approximate eigenelements. We analyze structured pseudospectra of structured matrix poly- nomials and establish a partial equality between unstructured and structured pseudospectra, which plays an important role in solving certain distance problems associated with structured polynomials. We also derive relatively simple expressions for structured condition numbers of simple eigenvalues of structured matrix polynomials, which play an important role in ana- lyzing sensitivity of eigenvalues of structured polynomial eigenvalue problem. Generally, a polynomial eigenvalue problem is \linearized"" Drst and then solved by a back- ward stable algorithm. However, the eigenvalues of the resulting linear problem is usually more sensitive to perturbation than the original problem. Moreover, a polynomial admits inDnitely many linearizations. The same holds true for structured polynomials as well. Therefore, for computational purposes, it is of paramount importance to identify potential structured lin- earizations which are as well conditioned as possible. With the help of structured backward perturbation analysis and structured condition numbers of eigenvalues, we identify \good"" structured linearizations which guarantee almost as accurate solutions as that of the original polynomial eigenvalue problem..

Browse

Browsing PhD Theses (Mathematics) by Title

Results Per Page

Sort Options