Search results for: Induced acyclic path decomposition

Authors: Abraham V. M., I. Sahul Hamid

Abstract:

A decomposition of a graph G is a collection ψ of graphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path in G, then ψ is called an induced acyclic path decomposition of G and if each Hi is a (induced) cycle in G then ψ is called a (induced) cycle decomposition of G. The minimum cardinality of an induced acyclic path decomposition of G is called the induced acyclic path decomposition number of G and is denoted by ¤Çia(G). Similarly the cyclic decomposition number ¤Çc(G) is defined. In this paper we begin an investigation of these parameters.

Keywords: Cycle decomposition, Induced acyclic path decomposition, Induced acyclic path decomposition number.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1517

Authors: K. Ratan Singh, P. K. Das

Abstract:

An induced acyclic graphoidal cover of a graph G is a collection ψ of open paths in G such that every path in ψ has atleast two vertices, every vertex of G is an internal vertex of at most one path in ψ, every edge of G is in exactly one path in ψ and every member of ψ is an induced path. The minimum cardinality of an induced acyclic graphoidal cover of G is called the induced acyclic graphoidal covering number of G and is denoted by ηia(G) or ηia. Here we find induced acyclic graphoidal cover for some classes of graphs.

Keywords: Graphoidal cover, Induced acyclic graphoidal cover, Induced acyclic graphoidal covering number.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1247

Authors: I. Sahul Hamid, Abraham V. M.

Abstract:

A decomposition of a graph G is a collection ψ of subgraphs H1,H2, . . . , Hr of G such that every edge of G belongs to exactly one Hi. If each Hi is either an induced path or an induced cycle in G, then ψ is called an induced path decomposition of G. The minimum cardinality of an induced path decomposition of G is called the induced path decomposition number of G and is denoted by πi(G). In this paper we initiate a study of this parameter.

Keywords: Path decomposition, Induced path decomposition, Induced path decomposition number.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2327

Authors: K. Ratan Singh, P. K. Das

Abstract:

An induced graphoidal cover of a graph G is a collection ψ of (not necessarily open) paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ, every edge of G is in exactly one path in ψ and every member of ψ is an induced cycle or an induced path. The minimum cardinality of an induced graphoidal cover of G is called the induced graphoidal covering number of G and is denoted by ηi(G) or ηi. Here we find induced graphoidal cover for some classes of graphs.

Keywords: Graphoidal cover, Induced graphoidal cover, Induced graphoidal covering number.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1386

Authors: Ahmad Salehi

Abstract:

An acyclic coloring of a graph G is a coloring of its vertices such that:(i) no two neighbors in G are assigned the same color and (ii) no bicolored cycle can exist in G. The acyclic chromatic number of G is the least number of colors necessary to acyclically color G. Recently it has been proved that any graph of maximum degree 5 has an acyclic chromatic number at most 8. In this paper we present another proof for this result.

Keywords: Acyclic Coloring, Vertex coloring.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1407

Authors: M. A. Koroma, S. Widatalla, A. F. Kamara, C. Zhang

Abstract:

Our aim in this piece of work is to demonstrate the power of the Laplace Adomian decomposition method (LADM) in approximating the solutions of nonlinear differential equations governing the two-dimensional viscous flow induced by a shrinking sheet.

Keywords: Adomian polynomials, Laplace Adomian decomposition method, Padé Approximant, Shrinking sheet.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1987

Authors: Mohammed Boutalline, Imad Badi, Belaid Bouikhalene, Said Safi

Abstract:

In this paper we describe the Levenvberg-Marquardt (LM) algorithm for identification and equalization of CDMA signals received by an antenna array in communication channels. The synthesis explains the digital separation and equalization of signals after propagation through multipath generating intersymbol interference (ISI). Exploiting discrete data transmitted and three diversities induced at the reception, the problem can be composed by the Block Component Decomposition (BCD) of a tensor of order 3 which is a new tensor decomposition generalizing the PARAFAC decomposition. We optimize the BCD decomposition by Levenvberg-Marquardt method gives encouraging results compared to classical alternating least squares algorithm (ALS). In the equalization part, we use the Minimum Mean Square Error (MMSE) to perform the presented method. The simulation results using the LM algorithm are important.

Keywords: Identification and equalization, communication channel, Levenvberg-Marquardt, tensor decomposition

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1779

Authors: Pradya Pornnimitkul, Suwich Kunaruttanapruk, Bamrung Tau Sieskul, Somchai Jitapunkul

Abstract:

In this paper, we investigate a blind channel estimation method for Multi-carrier CDMA systems that use a subspace decomposition technique. This technique exploits the orthogonality property between the noise subspace and the received user codes to obtain channel of each user. In the past we used Singular Value Decomposition (SVD) technique but SVD have most computational complexity so in this paper use a new algorithm called URV Decomposition, which serve as an intermediary between the QR decomposition and SVD, replaced in SVD technique to track the noise space of the received data. Because of the URV decomposition has almost the same estimation performance as the SVD, but has less computational complexity.

Keywords: Channel estimation, MC-CDMA, SVD, URV.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1735

Authors: Jürgen Beyer

Abstract:

In association with path dependence, researchers often talk of institutional “lock-in", thereby indicating that far-reaching path deviation or path departure are to be regarded as exceptional cases. This article submits the alleged general inclination for stability of path-dependent processes to a critical review. The different reasons for path dependence found in the literature indicate that different continuity-ensuring mechanisms are at work when people talk about path dependence (“increasing returns", complementarity, sequences etc.). As these mechanisms are susceptible to fundamental change in different ways and to different degrees, the path dependence concept alone is of only limited explanatory value. It is therefore indispensable to identify the underlying continuity-ensuring mechanism as well if a statement-s empirical value is to go beyond the trivial, always true “history matters".

Keywords: path dependence, increasing returns, historicalinstitutionalism, lock-in.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1807

Authors: Dragos Nicolae VIZIREANU

Abstract:

One of the main image representations in Mathematical Morphology is the 3D Shape Decomposition Representation, useful for Image Compression and Representation,and Pattern Recognition. The 3D Morphological Shape Decomposition representation can be generalized a number of times,to extend the scope of its algebraic characteristics as much as possible. With these generalizations, the Morphological Shape Decomposition 's role to serve as an efficient image decomposition tool is extended to grayscale images.This work follows the above line, and further develops it. Anew evolutionary branch is added to the 3D Morphological Shape Decomposition's development, by the introduction of a 3D Multi Structuring Element Morphological Shape Decomposition, which permits 3D Morphological Shape Decomposition of 3D binary images (grayscale images) into "multiparameter" families of elements. At the beginning, 3D Morphological Shape Decomposition representations are based only on "1 parameter" families of elements for image decomposition.This paper addresses the gray scale inter frame interpolation by means of mathematical morphology. The new interframe interpolation method is based on generalized morphological 3D Shape Decomposition. This article will present the theoretical background of the morphological interframe interpolation, deduce the new representation and show some application examples.Computer simulations could illustrate results.

Keywords: 3D shape decomposition representation, mathematical morphology, gray scale interframe interpolation

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1692

Authors: Jae Keun Park, Sung Je Hong, Kyong Hoon Kim, Tae Heum Kang, Wan Yeon Lee

Abstract:

In this paper, we propose a routing scheme that guarantees the residual lifetime of wireless sensor networks where each sensor node operates with a limited budget of battery energy. The scheme maximizes the communications QoS while sustaining the residual battery lifetime of the network for a specified duration. Communication paths of wireless nodes are translated into a directed acyclic graph(DAG) and the maximum-flow algorithm is applied to the graph. The found maximum flow are assigned to sender nodes, so as to maximize their communication QoS. Based on assigned flows, the scheme determines the routing path and the transmission rate of data packet so that any sensor node on the path would not exhaust its battery energy before a specified duration.

Keywords: Sensor network, battery, residual lifetime, routingscheme, QoS

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1587

Authors: Chang-le Lu, Yong Chen

Abstract:

The shortest path question is in a graph theory model question, and it is applied in many fields. The most short-path question may divide into two kinds: Single sources most short-path, all apexes to most short-path. This article mainly introduces the problem of all apexes to most short-path, and gives a new parallel algorithm of all apexes to most short-path according to the Dijkstra algorithm. At last this paper realizes the parallel algorithms in the technology of C # multithreading.

Keywords: Dijkstra algorithm, parallel algorithms, multi-thread technology, most short-path, ratio.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2040

Authors: Ruilian Zhao, Ling Lin

Abstract:

MM-Path, an acronym for Method/Message Path, describes the dynamic interactions between methods in object-oriented systems. This paper discusses the classifications of MM-Path, based on the characteristics of object-oriented software. We categorize it according to the generation reasons, the effect scope and the composition of MM-Path. A formalized representation of MM-Path is also proposed, which has considered the influence of state on response method sequences of messages. .Moreover, an automatic MM-Path generation approach based on UML Statechart diagram has been presented, and the difficulties in identifying and generating MM-Path can be solved. . As a result, it provides a solid foundation for further research on test cases generation based on MM-Path.

Keywords: MM-Path, Message Sequence, Object-Oriented Integration Testing, Response Method Sequence, UML Statechart Diagram.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2553

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. Given two graphs G and H, an H-decomposition of G is a partition of the edge set of G into disjoint isomorphic copies of H. An n-sun is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper we have proved that the complete graph of order 2n, K2n can be decomposed into n-2 n-suns, a Hamilton cycle and a perfect matching, when n is even and for odd case, the decomposition is n-1 n-suns and a perfect matching. For an odd order complete graph K2n+1, delete the star subgraph K1, 2n and the resultant graph K2n is decomposed as in the case of even order. The method of building n-suns uses Walecki's construction for the Hamilton decomposition of complete graphs. A spanning tree decomposition of even order complete graphs is also discussed using the labeling scheme of n-sun decomposition. A complete bipartite graph Kn, n can be decomposed into n/2 n-suns when n/2 is even. When n/2 is odd, Kn, n can be decomposed into (n-2)/2 n-suns and a Hamilton cycle.

Keywords: Hamilton cycle, n-sun decomposition, perfectmatching, spanning tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2209

Authors: Hamdy M. Youssef, Eman A. Al-Lehaibi

Abstract:

Due to many applications and problems in the fields of plasma physics, geophysics, and other many topics, the interaction between the strain field and the magnetic field has to be considered. Adomian introduced the decomposition method for solving linear and nonlinear functional equations. This method leads to accurate, computable, approximately convergent solutions of linear and nonlinear partial and ordinary differential equations even the equations with variable coefficients. This paper is dealing with a mathematical model of generalized thermoelasticity of a half-space conducting medium. A magnetic field with constant intensity acts normal to the bounding plane has been assumed. Adomian’s decomposition method has been used to solve the model when the bounding plane is taken to be traction free and thermally loaded by harmonic heating. The numerical results for the temperature increment, the stress, the strain, the displacement, the induced magnetic, and the electric fields have been represented in figures. The magnetic field, the relaxation time, and the angular thermal load have significant effects on all the studied fields.

Keywords: Adomian’s Decomposition Method, magneto-thermoelasticity, finite conductivity, iteration method, thermal load.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 741

Authors: M. Michalska-Domańska, P. Jóźwik, Z. Bojar

Abstract:

Intermetallic Ni3Al – based alloys belong to a group of advanced materials characterized by good chemical and physical properties (such as structural stability, corrosion resistance) which offer advenced technological applications. The paper presents the study of catalytic properties of Ni3Al foils (thickness approximately 50 &m) in the methanol and hexane decomposition. The egzamined material posses microcrystalline structure without any additional catalysts on the surface. The better catalytic activity of Ni3Al foils with respect to quartz plates in both methanol and hexane decomposition was confirmed. On thin Ni3Al foils the methanol conversion reaches approximately 100% above 480 oC while the hexane conversion reaches approximately 100% (98,5%) at 500 oC. Deposit formed during the methanol decomposition is built up of carbon nanofibers decorated with metal-like nanoparticles.

Keywords: hexane decomposition, methanol decomposition, Ni3Al thin foils, Ni nanoparticles

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1495

Authors: P.S.Prakash, S.Selvan

Abstract:

Over the past several years, there has been a considerable amount of research within the field of Quality of Service (QoS) support for distributed multimedia systems. One of the key issues in providing end-to-end QoS guarantees in packet networks is determining a feasible path that satisfies a number of QoS constraints. The problem of finding a feasible path is NPComplete if number of constraints is more than two and cannot be exactly solved in polynomial time. We proposed Feasible Path Selection Algorithm (FPSA) that addresses issues with pertain to finding a feasible path subject to delay and cost constraints and it offers higher success rate in finding feasible paths.

Keywords: feasible path, multiple constraints, path selection, QoS routing

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1700

Authors: Saad Al-Baddai, Karema Al-Subari, Elmar Lang, Bernd Ludwig

Abstract:

Empirical mode decomposition (EMD), a new data-driven of time-series decomposition, has the advantage of supposing that a time series is non-linear or non-stationary, as is implicitly achieved in Fourier decomposition. However, the EMD suffers of mode mixing problem in some cases. The aim of this paper is to present a solution for a common type of signals causing of EMD mode mixing problem, in case a signal suffers of an intermittency. By an artificial example, the solution shows superior performance in terms of cope EMD mode mixing problem comparing with the conventional EMD and Ensemble Empirical Mode decomposition (EEMD). Furthermore, the over-sifting problem is also completely avoided; and computation load is reduced roughly six times compared with EEMD, an ensemble number of 50.

Keywords: Empirical mode decomposition, mode mixing, sifting process, over-sifting.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 945

Authors: R. Anitha, R. S. Lekshmi

Abstract:

Graph decompositions are vital in the study of combinatorial design theory. A decomposition of a graph G is a partition of its edge set. An n-sun graph is a cycle Cn with an edge terminating in a vertex of degree one attached to each vertex. In this paper, we define n-sun decomposition of some even order graphs with a perfect matching. We have proved that the complete graph K2n, complete bipartite graph K2n, 2n and the Harary graph H4, 2n have n-sun decompositions. A labeling scheme is used to construct the n-suns.

Keywords: Decomposition, Hamilton cycle, n-sun graph, perfect matching, spanning tree.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2343

Authors: Young-Seok Choi

Abstract:

We present a subband adaptive infinite-impulse response (IIR) filtering method, which is based on a polyphase decomposition of IIR filter. Motivated by the fact that the polyphase structure has benefits in terms of convergence rate and stability, we introduce the polyphase decomposition to subband IIR filtering, i.e., in each subband high order IIR filter is decomposed into polyphase IIR filters with lower order. Computer simulations demonstrate that the proposed method has improved convergence rate over conventional IIR filters.

Keywords: Subband adaptive filter, IIR filtering. Polyphase decomposition.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2435

Authors: Liming Zhang

Abstract:

This paper introduces a new instantaneous frequency computation approach
-Counting Instantaneous Frequency for a general class of signals called simple waves. The classsimple wave contains a wide range of continuous signals for which the concept instantaneous frequency has a perfect physical sense. The concept of
-Counting Instantaneous Frequency also applies to all the discrete data. For all the simple wave signals and the discrete data,
-Counting instantaneous frequency can be computed directly without signal decomposition process. The intrinsic mode functions obtained through empirical mode decomposition belongs to simple wave. So
-Counting instantaneous frequency can be used together with empirical mode decomposition.

Keywords: Instantaneous frequency, empirical mode decomposition, intrinsic mode function.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1524

Authors: Liming Zhang

Abstract:

There have been different approaches to compute the analytic instantaneous frequency with a variety of background reasoning and applicability in practice, as well as restrictions. This paper presents an adaptive Fourier decomposition and (α-counting) based instantaneous frequency computation approach. The adaptive Fourier decomposition is a recently proposed new signal decomposition approach. The instantaneous frequency can be computed through the so called mono-components decomposed by it. Due to the fast energy convergency, the highest frequency of the signal will be discarded by the adaptive Fourier decomposition, which represents the noise of the signal in most of the situation. A new instantaneous frequency definition for a large class of so-called simple waves is also proposed in this paper. Simple wave contains a wide range of signals for which the concept instantaneous frequency has a perfect physical sense. The α-counting instantaneous frequency can be used to compute the highest frequency for a signal. Combination of these two approaches one can obtain the IFs of the whole signal. An experiment is demonstrated the computation procedure with promising results.

Keywords: Adaptive Fourier decomposition, Fourier series, signal processing, instantaneous frequency

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2307

Authors: Aki Happonen, Adrian Burian, Erwin Hemming

Abstract:

Fixed-point simulation results are used for the performance measure of inverting matrices by Cholesky decomposition. The fixed-point Cholesky decomposition algorithm is implemented using a fixed-point reconfigurable processing element. The reconfigurable processing element provides all mathematical operations required by Cholesky decomposition. The fixed-point word length analysis is based on simulations using different condition numbers and different matrix sizes. Simulation results show that 16 bits word length gives sufficient performance for small matrices with low condition number. Larger matrices and higher condition numbers require more dynamic range for a fixedpoint implementation.

Keywords: Cholesky Decomposition, Fixed-point, Matrix inversion, Reconfigurable processing.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1635

Authors: Lili Chen, Chao Yuan

Abstract:

On path space kQ, there is a trivial kQ^a-module structure determined by the multiplication of path algebra kQ^a and a trivial kQ^c-comodule structure determined by the comultiplication of path coalgebra kQ^c. In this paper, on path space kQ, a nontrivial kQ^a-module structure is defined, and it is proved that this nontrivial left kQ^a-module structure is isomorphic to the dual module structure of trivial right kQ^c-comodule. Dually, on path space kQ, a nontrivial kQ^c-comodule structure is defined, and it is proved that this nontrivial right kQ^c-comodule structure is isomorphic to the dual comodule structure of trivial left kQ^a-module. Finally, the trivial and nontrivial module structures on path space are compared from the aspect of submodule, and the trivial and nontrivial comodule structures on path space are compared from the aspect of subcomodule.

Keywords: Quiver, path space, module, comodule, dual.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 797

Authors: Divya Agarwal, Pushpendra S. Bharti

Abstract:

Autonomous mobile robots (AMR) are expected as smart tools for operations in every automation industry. Path planning and obstacle avoidance is the backbone of AMR as robots have to reach their goal location avoiding obstacles while traversing through optimized path defined according to some criteria such as distance, time or energy. Path planning can be classified into global and local path planning where environmental information is known and unknown/partially known, respectively. A number of sensors are used for data collection. A number of algorithms such as artificial potential field (APF), rapidly exploring random trees (RRT), bidirectional RRT, Fuzzy approach, Purepursuit, A* algorithm, vector field histogram (VFH) and modified local path planning algorithm, etc. have been used in the last three decades for path planning and obstacle avoidance for AMR. This paper makes an attempt to review some of the path planning and obstacle avoidance algorithms used in the field of AMR. The review includes comparative analysis of simulation and mathematical computations of path planning and obstacle avoidance algorithms using MATLAB 2018a. From the review, it could be concluded that different algorithms may complete the same task (i.e. with a different set of instructions) in less or more time, space, effort, etc.

Keywords: Autonomous mobile robots, obstacle avoidance, path planning, and processing time.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1628

Authors: Miloš Šeda

Abstract:

Finding the shortest path between two positions is a fundamental problem in transportation, routing, and communications applications. In robot motion planning, the robot should pass around the obstacles touching none of them, i.e. the goal is to find a collision-free path from a starting to a target position. This task has many specific formulations depending on the shape of obstacles, allowable directions of movements, knowledge of the scene, etc. Research of path planning has yielded many fundamentally different approaches to its solution, mainly based on various decomposition and roadmap methods. In this paper, we show a possible use of visibility graphs in point-to-point motion planning in the Euclidean plane and an alternative approach using Voronoi diagrams that decreases the probability of collisions with obstacles. The second application area, investigated here, is focused on problems of finding minimal networks connecting a set of given points in the plane using either only straight connections between pairs of points (minimum spanning tree) or allowing the addition of auxiliary points to the set to obtain shorter spanning networks (minimum Steiner tree).

Keywords: motion planning, spanning tree, Steiner tree, Delaunay triangulation, Voronoi diagram.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1472

Authors: Wei-Chih Su, Kuan-Peng Chen, Ming-Chung Tsai, Zheng-Yao Su

Abstract:

A new decomposition form is introduced in this report to establish a criterion for the bi-partite separability of Bell diagonal states. A such criterion takes a quadratic inequality of the coefficients of a given Bell diagonal states and can be derived via a simple algorithmic calculation of its invariants. In addition, the criterion can be extended to a quantum system of higher dimension.

Keywords: decomposition, bipartite separability, Bell diagonal states.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1612

Authors: Mahdi Nouri

Abstract:

In this paper Algebraic Riccati matrix equation is used for Eigen-decomposition of special structured matrices. This is achieved by similarity transformation and then using algebraic riccati matrix equation to triangulation of matrices. The process is decomposition of matrices into small and specially structured submatrices with low dimensions for fast and easy finding of Eigenpairs. Numerical and structural examples included showing the efficiency of present method.

Keywords: Riccati, matrix equation, eigenvalue problem, symmetric, bisymmetric, persymmetric, decomposition, canonical forms, Graphs theory, adjacency and Laplacian matrices.

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1761

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 2246

Authors: Chang Liu, Zishu He

Abstract:

Adaptive echo cancellers with two-path algorithm are applied to avoid the false adaptation during the double-talk situation. In the two-path algorithm, several transfer logic solutions have been proposed to control the filter update. This paper presents an improved transfer logic solution. It improves the convergence speed of the two-path algorithm, and allows the reduction of the memory elements and computational complexity. Results of simulations show the improved performance of the proposed solution.

Keywords: Acoustic echo cancellation, Echo return lossenhancement (ERLE), Two-path algorithm, Transfer logic

Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1708