Search results for: Polynomial.
117 A Fast Block-based Evolutional Algorithm for Combinatorial Problems
Authors: Huang, Wei-Hsiu Chang, Pei-Chann, Wang, Lien-Chun
Abstract:
The problems with high complexity had been the challenge in combinatorial problems. Due to the none-determined and polynomial characteristics, these problems usually face to unreasonable searching budget. Hence combinatorial optimizations attracted numerous researchers to develop better algorithms. In recent academic researches, most focus on developing to enhance the conventional evolutional algorithms and facilitate the local heuristics, such as VNS, 2-opt and 3-opt. Despite the performances of the introduction of the local strategies are significant, however, these improvement cannot improve the performance for solving the different problems. Therefore, this research proposes a meta-heuristic evolutional algorithm which can be applied to solve several types of problems. The performance validates BBEA has the ability to solve the problems even without the design of local strategies.
Keywords: Combinatorial problems, Artificial Chromosomes, Blocks Mining, Block Recombination
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1416116 The Problem of Using the Calculation of the Critical Path to Solver Instances of the Job Shop Scheduling Problem
Authors: Marco Antonio Cruz-Chávez, Juan Frausto-Solís, Fernando Ramos-Quintana
Abstract:
A procedure commonly used in Job Shop Scheduling Problem (JSSP) to evaluate the neighborhoods functions that use the non-deterministic algorithms is the calculation of the critical path in a digraph. This paper presents an experimental study of the cost of computation that exists when the calculation of the critical path in the solution for instances in which a JSSP of large size is involved. The results indicate that if the critical path is use in order to generate neighborhoods in the meta-heuristics that are used in JSSP, an elevated cost of computation exists in spite of the fact that the calculation of the critical path in any digraph is of polynomial complexity.
Keywords: Job Shop, CPM, critical path, neighborhood, meta-heuristic.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2301115 Comparing the Efficiency of Simpson’s 1/3 and 3/8 Rules for the Numerical Solution of First Order Volterra Integro-Differential Equations
Authors: N. M. Kamoh, D. G. Gyemang, M. C. Soomiyol
Abstract:
This paper compared the efficiency of Simpson’s 1/3 and 3/8 rules for the numerical solution of first order Volterra integro-differential equations. In developing the solution, collocation approximation method was adopted using the shifted Legendre polynomial as basis function. A block method approach is preferred to the predictor corrector method for being self-starting. Experimental results confirmed that the Simpson’s 3/8 rule is more efficient than the Simpson’s 1/3 rule.
Keywords: Collocation shifted Legendre polynomials, Simpson’s rule and Volterra integro-differential equations.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 974114 Modeling and Optimization of Process Parameters in PMEDM by Genetic Algorithm
Authors: Farhad Kolahan, Mohammad Bironro
Abstract:
This paper addresses modeling and optimization of process parameters in powder mixed electrical discharge machining (PMEDM). The process output characteristics include metal removal rate (MRR) and electrode wear rate (EWR). Grain size of Aluminum powder (S), concentration of the powder (C), discharge current (I) pulse on time (T) are chosen as control variables to study the process performance. The experimental results are used to develop the regression models based on second order polynomial equations for the different process characteristics. Then, a genetic algorithm (GA) has been employed to determine optimal process parameters for any desired output values of machining characteristics.
Keywords: Regression modeling, PMEDM, GeneticAlgorithm, Optimization.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1492113 Near-Lossless Image Coding based on Orthogonal Polynomials
Authors: Krishnamoorthy R, Rajavijayalakshmi K, Punidha R
Abstract:
In this paper, a near lossless image coding scheme based on Orthogonal Polynomials Transform (OPT) has been presented. The polynomial operators and polynomials basis operators are obtained from set of orthogonal polynomials functions for the proposed transform coding. The image is partitioned into a number of distinct square blocks and the proposed transform coding is applied to each of these individually. After applying the proposed transform coding, the transformed coefficients are rearranged into a sub-band structure. The Embedded Zerotree (EZ) coding algorithm is then employed to quantize the coefficients. The proposed transform is implemented for various block sizes and the performance is compared with existing Discrete Cosine Transform (DCT) transform coding scheme.Keywords: Near-lossless Coding, Orthogonal Polynomials Transform, Embedded Zerotree Coding
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1943112 Identification of Nonlinear Systems Structured by Hammerstein-Wiener Model
Authors: A. Brouri, F. Giri, A. Mkhida, F. Z. Chaoui, A. Elkarkri, M. L. Chhibat
Abstract:
Standard Hammerstein-Wiener models consist of a linear subsystem sandwiched by two memoryless nonlinearities. The problem of identifying Hammerstein-Wiener systems is addressed in the presence of linear subsystem of structure totally unknown and polynomial input and output nonlinearities. Presently, the system nonlinearities are allowed to be noninvertible. The system identification problem is dealt by developing a two-stage frequency identification method. First, the parameters of system nonlinearities are identified. In the second stage, a frequency approach is designed to estimate the linear subsystem frequency gain. All involved estimators are proved to be consistent.
Keywords: Nonlinear system identification, Hammerstein systems, Wiener systems, frequency identification.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2399111 Mathematical Modelling of Transport Phenomena in Radioactive Waste-Cement-Bentonite Matrix
Authors: Ilija Plecas, Uranija Kozmidis-Luburic, Radojica Pesic
Abstract:
The leaching rate of 137Cs from spent mix bead (anion and cation) exchange resins in a cement-bentonite matrix has been studied. Transport phenomena involved in the leaching of a radioactive material from a cement-bentonite matrix are investigated using three methods based on theoretical equations. These are: the diffusion equation for a plane source an equation for diffusion coupled to a firstorder equation and an empirical method employing a polynomial equation. The results presented in this paper are from a 25-year mortar and concrete testing project that will influence the design choices for radioactive waste packaging for a future Serbian radioactive waste disposal center.
Keywords: bentonite, cement , radioactive waste, composite, disposal, diffusion
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2285110 A High Order Theory for Functionally Graded Shell
Authors: V. V. Zozulya
Abstract:
New theory for functionally graded (FG) shell based on expansion of the equations of elasticity for functionally graded materials (GFMs) into Legendre polynomials series has been developed. Stress and strain tensors, vectors of displacements, traction and body forces have been expanded into Legendre polynomials series in a thickness coordinate. In the same way functions that describe functionally graded relations has been also expanded. Thereby all equations of elasticity including Hook-s law have been transformed to corresponding equations for Fourier coefficients. Then system of differential equations in term of displacements and boundary conditions for Fourier coefficients has been obtained. Cases of the first and second approximations have been considered in more details. For obtained boundary-value problems solution finite element (FE) has been used of Numerical calculations have been done with Comsol Multiphysics and Matlab.
Keywords: Shell, FEM, FGM, legendre polynomial.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1589109 Feature Selection Methods for an Improved SVM Classifier
Authors: Daniel Morariu, Lucian N. Vintan, Volker Tresp
Abstract:
Text categorization is the problem of classifying text documents into a set of predefined classes. After a preprocessing step, the documents are typically represented as large sparse vectors. When training classifiers on large collections of documents, both the time and memory restrictions can be quite prohibitive. This justifies the application of feature selection methods to reduce the dimensionality of the document-representation vector. In this paper, three feature selection methods are evaluated: Random Selection, Information Gain (IG) and Support Vector Machine feature selection (called SVM_FS). We show that the best results were obtained with SVM_FS method for a relatively small dimension of the feature vector. Also we present a novel method to better correlate SVM kernel-s parameters (Polynomial or Gaussian kernel).Keywords: Feature Selection, Learning with Kernels, SupportVector Machine, and Classification.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1826108 System Survivability in Networks in the Context of Defense/Attack Strategies: The Large Scale
Authors: A. Ben Yaghlane, M. N. Azaiez, M. Mrad
Abstract:
We investigate the large scale of networks in the context of network survivability under attack. We use appropriate techniques to evaluate and the attacker-based- and the defenderbased- network survivability. The attacker is unaware of the operated links by the defender. Each attacked link has some pre-specified probability to be disconnected. The defender choice is so that to maximize the chance of successfully sending the flow to the destination node. The attacker however will select the cut-set with the highest chance to be disabled in order to partition the network. Moreover, we extend the problem to the case of selecting the best p paths to operate by the defender and the best k cut-sets to target by the attacker, for arbitrary integers p,k>1. We investigate some variations of the problem and suggest polynomial-time solutions.Keywords: Defense/attack strategies, large scale, networks, partitioning a network.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1480107 Transient Heat Conduction in Nonuniform Hollow Cylinders with Time Dependent Boundary Condition at One Surface
Authors: Sen Yung Lee, Chih Cheng Huang, Te Wen Tu
Abstract:
A solution methodology without using integral transformation is proposed to develop analytical solutions for transient heat conduction in nonuniform hollow cylinders with time-dependent boundary condition at the outer surface. It is shown that if the thermal conductivity and the specific heat of the medium are in arbitrary polynomial function forms, the closed solutions of the system can be developed. The influence of physical properties on the temperature distribution of the system is studied. A numerical example is given to illustrate the efficiency and the accuracy of the solution methodology.Keywords: Analytical solution, nonuniform hollow cylinder, time-dependent boundary condition, transient heat conduction.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2858106 2D Rigid Registration of MR Scans using the 1d Binary Projections
Authors: Panos D. Kotsas
Abstract:
This paper presents the application of a signal intensity independent registration criterion for 2D rigid body registration of medical images using 1D binary projections. The criterion is defined as the weighted ratio of two projections. The ratio is computed on a pixel per pixel basis and weighting is performed by setting the ratios between one and zero pixels to a standard high value. The mean squared value of the weighted ratio is computed over the union of the one areas of the two projections and it is minimized using the Chebyshev polynomial approximation using n=5 points. The sum of x and y projections is used for translational adjustment and a 45deg projection for rotational adjustment. 20 T1- T2 registration experiments were performed and gave mean errors 1.19deg and 1.78 pixels. The method is suitable for contour/surface matching. Further research is necessary to determine the robustness of the method with regards to threshold, shape and missing data.Keywords: Medical image, projections, registration, rigid.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1345105 System Reduction Using Modified Pole Clustering and Modified Cauer Continued Fraction
Authors: Jay Singh, C. B. Vishwakarma, Kalyan Chatterjee
Abstract:
A mixed method by combining modified pole clustering technique and modified cauer continued fraction is proposed for reducing the order of the large-scale dynamic systems. The denominator polynomial of the reduced order model is obtained by using modified pole clustering technique while the coefficients of the numerator are obtained by modified cauer continued fraction. This method generated 'k' number of reduced order models for kth order reduction. The superiority of the proposed method has been elaborated through numerical example taken from the literature and compared with few existing order reduction methods.
Keywords: Modified Pole Clustering, Modified Cauer Continued Fraction, Order Reduction, Stability, Transfer Function.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1965104 Ten Limit Cycles in a Quintic Lyapunov System
Authors: Li Feng
Abstract:
In this paper, center conditions and bifurcation of limit cycles at the nilpotent critical point in a class of quintic polynomial differential system are investigated.With the help of computer algebra system MATHEMATICA, the first 10 quasi Lyapunov constants are deduced. As a result, sufficient and necessary conditions in order to have a center are obtained. The fact that there exist 10 small amplitude limit cycles created from the three order nilpotent critical point is also proved. Henceforth we give a lower bound of cyclicity of three-order nilpotent critical point for quintic Lyapunov systems. At last, we give an system which could bifurcate 10 limit circles.
Keywords: Three-order nilpotent critical point, center-focus problem, bifurcation of limit cycles, Quasi-Lyapunov constant.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1414103 Computational Aspects of Regression Analysis of Interval Data
Authors: Michal Cerny
Abstract:
We consider linear regression models where both input data (the values of independent variables) and output data (the observations of the dependent variable) are interval-censored. We introduce a possibilistic generalization of the least squares estimator, so called OLS-set for the interval model. This set captures the impact of the loss of information on the OLS estimator caused by interval censoring and provides a tool for quantification of this effect. We study complexity-theoretic properties of the OLS-set. We also deal with restricted versions of the general interval linear regression model, in particular the crisp input – interval output model. We give an argument that natural descriptions of the OLS-set in the crisp input – interval output cannot be computed in polynomial time. Then we derive easily computable approximations for the OLS-set which can be used instead of the exact description. We illustrate the approach by an example.
Keywords: Linear regression, interval-censored data, computational complexity.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1469102 Several Spectrally Non-Arbitrary Ray Patterns of Order 4
Authors: Ling Zhang, Feng Liu
Abstract:
A matrix is called a ray pattern matrix if its entries are either 0 or a ray in complex plane which originates from 0. A ray pattern A of order n is called spectrally arbitrary if the complex matrices in the ray pattern class of A give rise to all possible nth degree complex polynomial. Otherwise, it is said to be spectrally non-arbitrary ray pattern. We call that a spectrally arbitrary ray pattern A of order n is minimally spectrally arbitrary if any nonzero entry of A is replaced, then A is not spectrally arbitrary. In this paper, we find that is not spectrally arbitrary when n equals to 4 for any θ which is greater than or equal to 0 and less than or equal to n. In this article, we give several ray patterns A(θ) of order n that are not spectrally arbitrary for some θ which is greater than or equal to 0 and less than or equal to n. by using the nilpotent-Jacobi method. One example is given in our paper.
Keywords: Spectrally arbitrary, Nilpotent matrix, Ray patterns, sign patterns.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 610101 Intention Recognition using a Graph Representation
Authors: So-Jeong Youn, Kyung-Whan Oh
Abstract:
The human friendly interaction is the key function of a human-centered system. Over the years, it has received much attention to develop the convenient interaction through intention recognition. Intention recognition processes multimodal inputs including speech, face images, and body gestures. In this paper, we suggest a novel approach of intention recognition using a graph representation called Intention Graph. A concept of valid intention is proposed, as a target of intention recognition. Our approach has two phases: goal recognition phase and intention recognition phase. In the goal recognition phase, we generate an action graph based on the observed actions, and then the candidate goals and their plans are recognized. In the intention recognition phase, the intention is recognized with relevant goals and user profile. We show that the algorithm has polynomial time complexity. The intention graph is applied to a simple briefcase domain to test our model.Keywords: Intention recognition, intention, graph, HCI.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3395100 Flexible Heuristics for Project Scheduling with Limited Resources
Authors: Miloš Šeda
Abstract:
Resource-constrained project scheduling is an NPhard optimisation problem. There are many different heuristic strategies how to shift activities in time when resource requirements exceed their available amounts. These strategies are frequently based on priorities of activities. In this paper, we assume that a suitable heuristic has been chosen to decide which activities should be performed immediately and which should be postponed and investigate the resource-constrained project scheduling problem (RCPSP) from the implementation point of view. We propose an efficient routine that, instead of shifting the activities, extends their duration. It makes it possible to break down their duration into active and sleeping subintervals. Then we can apply the classical Critical Path Method that needs only polynomial running time. This algorithm can simply be adapted for multiproject scheduling with limited resources.Keywords: Project management, resource-constrained scheduling, NP-hard problem, CPM, heuristic method.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 140999 Optimization of Slider Crank Mechanism Using Design of Experiments and Multi-Linear Regression
Authors: Galal Elkobrosy, Amr M. Abdelrazek, Bassuny M. Elsouhily, Mohamed E. Khidr
Abstract:
Crank shaft length, connecting rod length, crank angle, engine rpm, cylinder bore, mass of piston and compression ratio are the inputs that can control the performance of the slider crank mechanism and then its efficiency. Several combinations of these seven inputs are used and compared. The throughput engine torque predicted by the simulation is analyzed through two different regression models, with and without interaction terms, developed according to multi-linear regression using LU decomposition to solve system of algebraic equations. These models are validated. A regression model in seven inputs including their interaction terms lowered the polynomial degree from 3rd degree to 1st degree and suggested valid predictions and stable explanations.
Keywords: Design of experiments, regression analysis, SI Engine, statistical modeling.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 125198 Friction Behavior of Wood-Plastic Composites against Uncoated Cemented Carbide
Authors: A. Vilutis, V. Jankauskas
Abstract:
The paper presents the results of the investigation of the dry sliding friction of wood-plastic composites (WPCs) against tungsten carbide-cobalt (WC-Co) hard alloy. The dependence of the dynamic coefficient of friction on the main influencing factors (vertical load, temperature, and sliding distance) was investigated by evaluating their mutual interaction. Multiple regression analysis showed a high polynomial dependence (adjusted R2 > 0.98). The resistance of the composite to thermo-mechanical effects determines how temperature and force factors affect the magnitude of the coefficient of friction. WPC-B composite has the lowest friction and highest resistance compared to WPC-A, while composite and cemented carbide materials wear the least. Energy Dispersive Spectroscopy (EDS), based on elemental composition, provided important insights into the friction process.
Keywords: Friction, composite, carbide, temperature.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 7297 Relation between Roots and Tangent Lines of Function in Fractional Dimensions: A Method for Optimization Problems
Authors: Ali Dorostkar
Abstract:
In this paper, a basic schematic of fractional dimensional optimization problem is presented. As will be shown, a method is performed based on a relation between roots and tangent lines of function in fractional dimensions for an arbitrary initial point. It is shown that for each polynomial function with order N at least N tangent lines must be existed in fractional dimensions of 0 < α < N+1 which pass exactly through the all roots of the proposed function. Geometrical analysis of tangent lines in fractional dimensions is also presented to clarify more intuitively the proposed method. Results show that with an appropriate selection of fractional dimensions, we can directly find the roots. Method is presented for giving a different direction of optimization problems by the use of fractional dimensions.
Keywords: Tangent line, fractional dimension, root, optimization problem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 56396 Influence of Replacement Used Reference Coordinate System for Georeferencing of the Old Map of Europe
Authors: Jakub Havlicek, Jiri Cajthaml
Abstract:
The article describes the effect of the replacement of the used reference coordinate system in the georeferencing of an old map of Europe. The map was georeferenced into three types of projection – the equal-area conic (original cartographic projection), cylindrical Plate Carrée and cylindrical Mercator map projection. The map was georeferenced by means of the affine and the second-order polynomial transformation. The resulting georeferenced raster datasets from the Plate Carrée and Mercator projection were projected into the equal-area conic projection by means of projection equations. The output is the comparison of drawn graphics, the magnitude of standard deviations for individual projections and types of transformation.Keywords: Georeferencing, reference coordinate system, transformation, standard deviation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 154695 Numerical Studies of Galerkin-type Time-discretizations Applied to Transient Convection-diffusion-reaction Equations
Authors: Naveed Ahmed, Gunar Matthies
Abstract:
We deal with the numerical solution of time-dependent convection-diffusion-reaction equations. We combine the local projection stabilization method for the space discretization with two different time discretization schemes: the continuous Galerkin-Petrov (cGP) method and the discontinuous Galerkin (dG) method of polynomial of degree k. We establish the optimal error estimates and present numerical results which shows that the cGP(k) and dG(k)- methods are accurate of order k +1, respectively, in the whole time interval. Moreover, the cGP(k)-method is superconvergent of order 2k and dG(k)-method is of order 2k +1 at the discrete time points. Furthermore, the dependence of the results on the choice of the stabilization parameter are discussed and compared.
Keywords: Convection-diffusion-reaction equations, stabilized finite elements, discontinuous Galerkin, continuous Galerkin-Petrov.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 174994 The Knapsack Sharing Problem: A Tree Search Exact Algorithm
Authors: Mhand Hifi, Hedi Mhalla
Abstract:
In this paper, we study the knapsack sharing problem, a variant of the well-known NP-Hard single knapsack problem. We investigate the use of a tree search for optimally solving the problem. The used method combines two complementary phases: a reduction interval search phase and a branch and bound procedure one. First, the reduction phase applies a polynomial reduction strategy; that is used for decomposing the problem into a series of knapsack problems. Second, the tree search procedure is applied in order to attain a set of optimal capacities characterizing the knapsack problems. Finally, the performance of the proposed optimal algorithm is evaluated on a set of instances of the literature and its runtime is compared to the best exact algorithm of the literature.
Keywords: Branch and bound, combinatorial optimization, knap¬sack, knapsack sharing, heuristics, interval reduction.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 155893 The Relationship between Land Use Change and Runoff
Authors: Thanutch Sukwimolseree, Preeyaphorn Kosa
Abstract:
Many problems are occurred in watershed due to human activity and economic development. The purpose is to determine the effects of the land use change on surface runoff using land use map on 1980, 2001 and 2008 and daily weather data during January 1, 1979 to September 30, 2010 applied to SWAT. The results can be presented that the polynomial equation is suitable to display that relationship. These equations for land use in 1980, 2001 and 2008 are consisted of y = -0.0076x5 + 0.1914x4–1.6386x3 + 6.6324x2–8.736x + 7.8023(R2 = 0.9255), y = -0.0298x5 + 0.8794x4 - 9.8056x3 + 51.99x2 - 117.04x + 96.797; (R2 = 0.9186) and y = -0.0277x5 + 0.8132x4 - 8.9598x3 + 46.498x2–101.83x +81.108 (R2 = 0.9006), respectively. Moreover, if the agricultural area is the largest area, it is a sensitive parameter to concern surface runoff.
Keywords: Land use, Runoff, SWAT, Upper Mun River Basin.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 236692 Boundary-Element-Based Finite Element Methods for Helmholtz and Maxwell Equations on General Polyhedral Meshes
Authors: Dylan M. Copeland
Abstract:
We present new finite element methods for Helmholtz and Maxwell equations on general three-dimensional polyhedral meshes, based on domain decomposition with boundary elements on the surfaces of the polyhedral volume elements. The methods use the lowest-order polynomial spaces and produce sparse, symmetric linear systems despite the use of boundary elements. Moreover, piecewise constant coefficients are admissible. The resulting approximation on the element surfaces can be extended throughout the domain via representation formulas. Numerical experiments confirm that the convergence behavior on tetrahedral meshes is comparable to that of standard finite element methods, and equally good performance is attained on more general meshes.
Keywords: Boundary elements, finite elements, Helmholtz equation, Maxwell equations.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 172491 Computing Maximum Uniquely Restricted Matchings in Restricted Interval Graphs
Authors: Swapnil Gupta, C. Pandu Rangan
Abstract:
A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.Keywords: Uniquely restricted matching, interval graph, design and analysis of algorithms, matching, induced matching, witness counting.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 154690 Aliasing Free and Additive Error in Spectra for Alpha Stable Signals
Authors: R. Sabre
Abstract:
This work focuses on the symmetric alpha stable process with continuous time frequently used in modeling the signal with indefinitely growing variance, often observed with an unknown additive error. The objective of this paper is to estimate this error from discrete observations of the signal. For that, we propose a method based on the smoothing of the observations via Jackson polynomial kernel and taking into account the width of the interval where the spectral density is non-zero. This technique allows avoiding the “Aliasing phenomenon” encountered when the estimation is made from the discrete observations of a process with continuous time. We have studied the convergence rate of the estimator and have shown that the convergence rate improves in the case where the spectral density is zero at the origin. Thus, we set up an estimator of the additive error that can be subtracted for approaching the original signal without error.
Keywords: Spectral density, stable processes, aliasing, p-adic.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 58489 Effect of Time Delay on the Transmission of Dengue Fever
Authors: K. Patanarapelert, I.M. Tang
Abstract:
The effect of a time delay on the transmission on dengue fever is studied. The time delay is due to the presence of an incubation period for the dengue virus to develop in the mosquito before the mosquito becomes infectious. The conditions for the existence of a Hopf bifurcation to limit cycle behavior are established. The conditions are different from the usual one and they are based on whether a particular third degree polynomial has positive real roots. A theorem for determining whether for a given set of parameter values, a critical delay time exist is given. It is found that for a set of realistic values of the parameters in the model, a Hopf bifurcation can not occur. For a set of unrealistic values of some of the parameters, it is shown that a Hopf bifurcation can occur. Numerical solutions using this last set show the trajectory of two of the variables making a transition from a spiraling orbit to a limit cycle orbit.Keywords: Dengue fever transmission, time delay, Hopfbifurcation, limit cycle behavior
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 179188 Nonlinear Dynamics of Cracked RC Beams under Harmonic Excitation
Authors: Atul Krishna Banik
Abstract:
Nonlinear response behaviour of a cracked RC beam under harmonic excitation is analysed to investigate various instability phenomena like, bifurcation, jump phenomena etc. The nonlinearity of the system arises due to opening and closing of the cracks in the RC beam and is modelled as a cubic polynomial. In order to trace different branches at the bifurcation point on the response curve (amplitude versus frequency of excitation plot), an arc length continuation technique along with the incremental harmonic balance (IHBC) method is employed. The stability of the solution is investigated by the Floquet theory using Hsu-s scheme. The periodic solutions obtained by the IHBC method are compared with these obtained by the numerical integration of the equation of motion. Characteristics of solutions fold bifurcation, jump phenomena and from stable to unstable zones are identified.
Keywords: Incremental harmonic balance, arc-length continuation, bifurcation, jump phenomena.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1520