Search results for: Graph computation
497 A New Composition Method of Admissible Support Vector Kernel Based on Reproducing Kernel
Authors: Wei Zhang, Xin Zhao, Yi-Fan Zhu, Xin-Jian Zhang
Abstract:
Kernel function, which allows the formulation of nonlinear variants of any algorithm that can be cast in terms of dot products, makes the Support Vector Machines (SVM) have been successfully applied in many fields, e.g. classification and regression. The importance of kernel has motivated many studies on its composition. It-s well-known that reproducing kernel (R.K) is a useful kernel function which possesses many properties, e.g. positive definiteness, reproducing property and composing complex R.K by simple operation. There are two popular ways to compute the R.K with explicit form. One is to construct and solve a specific differential equation with boundary value whose handicap is incapable of obtaining a unified form of R.K. The other is using a piecewise integral of the Green function associated with a differential operator L. The latter benefits the computation of a R.K with a unified explicit form and theoretical analysis, whereas there are relatively later studies and fewer practical computations. In this paper, a new algorithm for computing a R.K is presented. It can obtain the unified explicit form of R.K in general reproducing kernel Hilbert space. It avoids constructing and solving the complex differential equations manually and benefits an automatic, flexible and rigorous computation for more general RKHS. In order to validate that the R.K computed by the algorithm can be used in SVM well, some illustrative examples and a comparison between R.K and Gaussian kernel (RBF) in support vector regression are presented. The result shows that the performance of R.K is close or slightly superior to that of RBF.
Keywords: admissible support vector kernel, reproducing kernel, reproducing kernel Hilbert space, Green function, support vectorregression
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1542496 Spatial Integration at the Room-Level of 'Sequina' Slum Area in Alexandria, Egypt
Authors: Ali Essam El Shazly
Abstract:
The social logic of 'Sequina' slum area in Alexandria details the integral measure of space syntax at the room-level of twenty-building samples. The essence of spatial structure integrates the central 'visitor' domain with the 'living' frontage of the 'children' zone against the segregated privacy of the opposite 'parent' depth. Meanwhile, the multifunctioning of shallow rooms optimizes the integral 'visitor' structure through graph and visibility dimensions in contrast to the 'inhabitant' structure of graph-tails out of sight. Common theme of the layout integrity increases in compensation to the decrease of room visibility. Despite the 'pheno-type' of collective integration, the individual layouts observe 'geno-type' structure of spatial diversity per room adjoins. In this regard, the layout integrity alternates the cross-correlation of the 'kitchen & living' rooms with the 'inhabitant & visitor' domains of 'motherhood' dynamic structure. Moreover, the added 'grandparent' restructures the integral measure to become the deepest space, but opens to the 'living' of 'household' integrity. Some isomorphic layouts change the integral structure just through the 'balcony' extension of access, visual or ignored 'ringiness' of space syntax. However, the most integrated or segregated layouts invert the 'geno-type' into a shallow 'inhabitant' centrality versus the remote 'visitor' structure. Overview of the multivariate social logic of spatial integrity could never clarify without the micro-data analysis.Keywords: Alexandria, Sequina slum, spatial integration, space syntax.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1436495 Sign Pattern Matrices that Admit P0 Matrices
Authors: Ling Zhang, Ting-Zhu Huang
Abstract:
A P0-matrix is a real square matrix all of whose principle minors are nonnegative. In this paper, we consider the class of P0-matrix. Our main aim is to determine which sign pattern matrices are admissible for this class of real matrices.
Keywords: Sign pattern matrices, P0 matrices, graph, digraph.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1219494 Likelihood Estimation for Stochastic Epidemics with Heterogeneous Mixing Populations
Authors: Yilun Shang
Abstract:
We consider a heterogeneously mixing SIR stochastic epidemic process in populations described by a general graph. Likelihood theory is developed to facilitate statistic inference for the parameters of the model under complete observation. We show that these estimators are asymptotically Gaussian unbiased estimates by using a martingale central limit theorem.Keywords: statistic inference, maximum likelihood, epidemicmodel, heterogeneous mixing.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1408493 An Energy Aware Data Aggregation in Wireless Sensor Network Using Connected Dominant Set
Authors: M. Santhalakshmi, P Suganthi
Abstract:
Wireless Sensor Networks (WSNs) have many advantages. Their deployment is easier and faster than wired sensor networks or other wireless networks, as they do not need fixed infrastructure. Nodes are partitioned into many small groups named clusters to aggregate data through network organization. WSN clustering guarantees performance achievement of sensor nodes. Sensor nodes energy consumption is reduced by eliminating redundant energy use and balancing energy sensor nodes use over a network. The aim of such clustering protocols is to prolong network life. Low Energy Adaptive Clustering Hierarchy (LEACH) is a popular protocol in WSN. LEACH is a clustering protocol in which the random rotations of local cluster heads are utilized in order to distribute energy load among all sensor nodes in the network. This paper proposes Connected Dominant Set (CDS) based cluster formation. CDS aggregates data in a promising approach for reducing routing overhead since messages are transmitted only within virtual backbone by means of CDS and also data aggregating lowers the ratio of responding hosts to the hosts existing in virtual backbones. CDS tries to increase networks lifetime considering such parameters as sensors lifetime, remaining and consumption energies in order to have an almost optimal data aggregation within networks. Experimental results proved CDS outperformed LEACH regarding number of cluster formations, average packet loss rate, average end to end delay, life computation, and remaining energy computation.Keywords: Wireless sensor network, connected dominant set, clustering, data aggregation.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1129492 Accelerating Quantum Chemistry Calculations: Machine Learning for Efficient Evaluation of Electron-Repulsion Integrals
Authors: Nishant Rodrigues, Nicole Spanedda, Chilukuri K. Mohan, Arindam Chakraborty
Abstract:
A crucial objective in quantum chemistry is the computation of the energy levels of chemical systems. This task requires electron-repulsion integrals as inputs and the steep computational cost of evaluating these integrals poses a major numerical challenge in efficient implementation of quantum chemical software. This work presents a moment-based machine learning approach for the efficient evaluation of electron-repulsion integrals. These integrals were approximated using linear combinations of a small number of moments. Machine learning algorithms were applied to estimate the coefficients in the linear combination. A random forest approach was used to identify promising features using a recursive feature elimination approach, which performed best for learning the sign of each coefficient, but not the magnitude. A neural network with two hidden layers was then used to learn the coefficient magnitudes, along with an iterative feature masking approach to perform input vector compression, identifying a small subset of orbitals whose coefficients are sufficient for the quantum state energy computation. Finally, a small ensemble of neural networks (with a median rule for decision fusion) was shown to improve results when compared to a single network.
Keywords: Quantum energy calculations, atomic orbitals, electron-repulsion integrals, ensemble machine learning, random forests, neural networks, feature extraction.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 186491 Some New Bounds for a Real Power of the Normalized Laplacian Eigenvalues
Authors: Ayşe Dilek Maden
Abstract:
For a given a simple connected graph, we present some new bounds via a new approach for a special topological index given by the sum of the real number power of the non-zero normalized Laplacian eigenvalues. To use this approach presents an advantage not only to derive old and new bounds on this topic but also gives an idea how some previous results in similar area can be developed.
Keywords: Degree Kirchhoff index, normalized Laplacian eigenvalue, spanning tree.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2201490 Decomposition of Graphs into Induced Paths and Cycles
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 2373489 Maximum Induced Subgraph of an Augmented Cube
Authors: Meng-Jou Chien, Jheng-Cheng Chen, Chang-Hsiung Tsai
Abstract:
Let maxζG(m) denote the maximum number of edges in a subgraph of graph G induced by m nodes. The n-dimensional augmented cube, denoted as AQn, a variation of the hypercube, possesses some properties superior to those of the hypercube. We study the cases when G is the augmented cube AQn.
Keywords: Interconnection network, Augmented cube, Induced subgraph, Bisection width.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1542488 Lower Bounds of Some Small Ramsey Numbers
Authors: Decha Samana, Vites Longani
Abstract:
For positive integer s and t, the Ramsey number R(s, t) is the least positive integer n such that for every graph G of order n, either G contains Ks as a subgraph or G contains Kt as a subgraph. We construct the circulant graphs and use them to obtain lower bounds of some small Ramsey numbers.Keywords: Lower bound, Ramsey numbers, Graphs, Distance line.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1374487 Computational Algorithm for Obtaining Abelian Subalgebras in Lie Algebras
Authors: Manuel Ceballos, Juan Nunez, Angel F. Tenorio
Abstract:
The set of all abelian subalgebras is computationally obtained for any given finite-dimensional Lie algebra, starting from the nonzero brackets in its law. More concretely, an algorithm is described and implemented to compute a basis for each nontrivial abelian subalgebra with the help of the symbolic computation package MAPLE. Finally, it is also shown a brief computational study for this implementation, considering both the computing time and the used memory.Keywords: Solvable Lie algebra, maximal abelian dimension, algorithm.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1282486 Investigating Transformations in the Cartesian Plane Using Spreadsheets
Authors: D. Allison, A. Didenko, G. Miller
Abstract:
The link between coordinate transformations in the plane and their effects on the graph of a function can be difficult for students studying college level mathematics to comprehend. To solidify this conceptual link in the mind of a student Microsoft Excel can serve as a convenient graphing tool and pedagogical aid. The authors of this paper describe how various transformations and their related functional symmetry properties can be graphically displayed with an Excel spreadsheet.
Keywords: Mathematics education, Microsoft Excel spreadsheet, technology.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1988485 Prime Cordial Labeling on Graphs
Authors: S. Babitha, J. Baskar Babujee
Abstract:
A prime cordial labeling of a graph G with vertex set V is a bijection f from V to {1, 2, ..., |V |} such that each edge uv is assigned the label 1 if gcd(f(u), f(v)) = 1 and 0 if gcd(f(u), f(v)) > 1, then the number of edges labeled with 0 and the number of edges labeled with 1 differ by at most 1. In this paper we exhibit some characterization results and new constructions on prime cordial graphs.
Keywords: Prime cordial, tree, Euler, bijective, function.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3576484 Probabilistic Graphical Model for the Web
Authors: M. Nekri, A. Khelladi
Abstract:
The world wide web network is a network with a complex topology, the main properties of which are the distribution of degrees in power law, A low clustering coefficient and a weak average distance. Modeling the web as a graph allows locating the information in little time and consequently offering a help in the construction of the research engine. Here, we present a model based on the already existing probabilistic graphs with all the aforesaid characteristics. This work will consist in studying the web in order to know its structuring thus it will enable us to modelize it more easily and propose a possible algorithm for its exploration.
Keywords: Clustering coefficient, preferential attachment, small world, Web community.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1604483 The Partial Non-combinatorially Symmetric N10 -Matrix Completion Problem
Authors: Gu-Fang Mou, Ting-Zhu Huang
Abstract:
An n×n matrix is called an N1 0 -matrix if all principal minors are non-positive and each entry is non-positive. In this paper, we study the partial non-combinatorially symmetric N1 0 -matrix completion problems if the graph of its specified entries is a transitive tournament or a double cycle. In general, these digraphs do not have N1 0 -completion. Therefore, we have given sufficient conditions that guarantee the existence of the N1 0 -completion for these digraphs.
Keywords: Matrix completion, matrix completion, N10 -matrix, non-combinatorially symmetric, cycle, digraph.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1085482 Distributed Data-Mining by Probability-Based Patterns
Authors: M. Kargar, F. Gharbalchi
Abstract:
In this paper a new method is suggested for distributed data-mining by the probability patterns. These patterns use decision trees and decision graphs. The patterns are cared to be valid, novel, useful, and understandable. Considering a set of functions, the system reaches to a good pattern or better objectives. By using the suggested method we will be able to extract the useful information from massive and multi-relational data bases.Keywords: Data-mining, Decision tree, Decision graph, Pattern, Relationship.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1554481 Computing SAGB-Gröbner Basis of Ideals of Invariant Rings by Using Gaussian Elimination
Authors: Sajjad Rahmany, Abdolali Basiri
Abstract:
The link between Gröbner basis and linear algebra was described by Lazard [4,5] where he realized the Gr┬¿obner basis computation could be archived by applying Gaussian elimination over Macaulay-s matrix . In this paper, we indicate how same technique may be used to SAGBI- Gröbner basis computations in invariant rings.Keywords: Gröbner basis, SAGBI- Gröbner basis, reduction, Invariant ring, permutation groups.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2999480 Numerical Study of Flapping-Wing Flight of Hummingbird Hawkmoth during Hovering: Longitudinal Dynamics
Authors: Yao Jie, Yeo Khoon Seng
Abstract:
In recent decades, flapping wing aerodynamics has attracted great interest. Understanding the physics of biological flyers such as birds and insects can help improve the performance of micro air vehicles. The present research focuses on the aerodynamics of insect-like flapping wing flight with the approach of numerical computation. Insect model of hawkmoth is adopted in the numerical study with rigid wing assumption currently. The numerical model integrates the computational fluid dynamics of the flow and active control of wing kinematics to achieve stable flight. The computation grid is a hybrid consisting of background Cartesian nodes and clouds of mesh-free grids around immersed boundaries. The generalized finite difference method is used in conjunction with single value decomposition (SVD-GFD) in computational fluid dynamics solver to study the dynamics of a free hovering hummingbird hawkmoth. The longitudinal dynamics of the hovering flight is governed by three control parameters, i.e., wing plane angle, mean positional angle and wing beating frequency. In present work, a PID controller works out the appropriate control parameters with the insect motion as input. The controller is adjusted to acquire desired maneuvering of the insect flight. The numerical scheme in present study is proven to be accurate and stable to simulate the flight of the hummingbird hawkmoth, which has relatively high Reynolds number. The PID controller is responsive to provide feedback to the wing kinematics during the hovering flight. The simulated hovering flight agrees well with the real insect flight. The present numerical study offers a promising route to investigate the free flight aerodynamics of insects, which could overcome some of the limitations of experiments.
Keywords: Aerodynamics, flight control, computational fluid dynamics, flapping-wing flight.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1451479 A Novel Recursive Multiplierless Algorithm for 2-D DCT
Authors: V.K.Ananthashayana, Geetha.K.S
Abstract:
In this paper, a recursive algorithm for the computation of 2-D DCT using Ramanujan Numbers is proposed. With this algorithm, the floating-point multiplication is completely eliminated and hence the multiplierless algorithm can be implemented using shifts and additions only. The orthogonality of the recursive kernel is well maintained through matrix factorization to reduce the computational complexity. The inherent parallel structure yields simpler programming and hardware implementation and provides log 1 2 3 2 N N-N+ additions and N N 2 log 2 shifts which is very much less complex when compared to other recent multiplierless algorithms.Keywords: DCT, Multilplerless, Ramanujan Number, Recursive.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1544478 Sensitivity Computations of Time Relaxation Model with an Application in Cavity Computation
Authors: Monika Neda, Elena Nikonova
Abstract:
We present a numerical study of the sensitivity of the so called time relaxation family of models of fluid motion with respect to the time relaxation parameter χ on the two dimensional cavity problem. The goal of the study is to compute and compare the sensitivity of the model using finite difference method (FFD) and sensitivity equation method (SEM).
Keywords: Sensitivity, time relaxation, deconvolution, Navier- Stokes equations.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1329477 Real-Time Vision-based Korean Finger Spelling Recognition System
Authors: Anjin Park, Sungju Yun, Jungwhan Kim, Seungk Min, Keechul Jung
Abstract:
Finger spelling is an art of communicating by signs made with fingers, and has been introduced into sign language to serve as a bridge between the sign language and the verbal language. Previous approaches to finger spelling recognition are classified into two categories: glove-based and vision-based approaches. The glove-based approach is simpler and more accurate recognizing work of hand posture than vision-based, yet the interfaces require the user to wear a cumbersome and carry a load of cables that connected the device to a computer. In contrast, the vision-based approaches provide an attractive alternative to the cumbersome interface, and promise more natural and unobtrusive human-computer interaction. The vision-based approaches generally consist of two steps: hand extraction and recognition, and two steps are processed independently. This paper proposes real-time vision-based Korean finger spelling recognition system by integrating hand extraction into recognition. First, we tentatively detect a hand region using CAMShift algorithm. Then fill factor and aspect ratio estimated by width and height estimated by CAMShift are used to choose candidate from database, which can reduce the number of matching in recognition step. To recognize the finger spelling, we use DTW(dynamic time warping) based on modified chain codes, to be robust to scale and orientation variations. In this procedure, since accurate hand regions, without holes and noises, should be extracted to improve the precision, we use graph cuts algorithm that globally minimize the energy function elegantly expressed by Markov random fields (MRFs). In the experiments, the computational times are less than 130ms, and the times are not related to the number of templates of finger spellings in database, as candidate templates are selected in extraction step.Keywords: CAMShift, DTW, Graph Cuts, MRF.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1635476 Translator Design to Model Cpp Files
Authors: Er. Satwinder Singh, Dr. K.S. Kahlon, Rakesh Kumar, Er. Gurjeet Singh
Abstract:
The most reliable and accurate description of the actual behavior of a software system is its source code. However, not all questions about the system can be answered directly by resorting to this repository of information. What the reverse engineering methodology aims at is the extraction of abstract, goal-oriented “views" of the system, able to summarize relevant properties of the computation performed by the program. While concentrating on reverse engineering we had modeled the C++ files by designing the translator.
Keywords: Translator, Modeling, UML, DYNO, ISVis, TED.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1533475 Optimal Path Planner for Autonomous Vehicles
Authors: M. Imran Akram, Ahmed Pasha, Nabeel Iqbal
Abstract:
In this paper a real-time trajectory generation algorithm for computing 2-D optimal paths for autonomous aerial vehicles has been discussed. A dynamic programming approach is adopted to compute k-best paths by minimizing a cost function. Collision detection is implemented to detect intersection of the paths with obstacles. Our contribution is a novel approach to the problem of trajectory generation that is computationally efficient and offers considerable gain over existing techniques.Keywords: dynamic programming, graph search, path planning.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2002474 Genetic Programming: Principles, Applications and Opportunities for Hydrological Modelling
Authors: Oluwaseun K. Oyebode, Josiah A. Adeyemo
Abstract:
Hydrological modelling plays a crucial role in the planning and management of water resources, most especially in water stressed regions where the need to effectively manage the available water resources is of critical importance. However, due to the complex, nonlinear and dynamic behaviour of hydro-climatic interactions, achieving reliable modelling of water resource systems and accurate projection of hydrological parameters are extremely challenging. Although a significant number of modelling techniques (process-based and data-driven) have been developed and adopted in that regard, the field of hydrological modelling is still considered as one that has sluggishly progressed over the past decades. This is majorly as a result of the identification of some degree of uncertainty in the methodologies and results of techniques adopted. In recent times, evolutionary computation (EC) techniques have been developed and introduced in response to the search for efficient and reliable means of providing accurate solutions to hydrological related problems. This paper presents a comprehensive review of the underlying principles, methodological needs and applications of a promising evolutionary computation modelling technique – genetic programming (GP). It examines the specific characteristics of the technique which makes it suitable to solving hydrological modelling problems. It discusses the opportunities inherent in the application of GP in water related-studies such as rainfall estimation, rainfall-runoff modelling, streamflow forecasting, sediment transport modelling, water quality modelling and groundwater modelling among others. Furthermore, the means by which such opportunities could be harnessed in the near future are discussed. In all, a case for total embracement of GP and its variants in hydrological modelling studies is made so as to put in place strategies that would translate into achieving meaningful progress as it relates to modelling of water resource systems, and also positively influence decision-making by relevant stakeholders.
Keywords: Computational modelling, evolutionary algorithms, genetic programming, hydrological modelling.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 3329473 Analysis of Social Network Using Clever Ant Colony Metaphor
Authors: Mohammad Al-Fayoumi, Soumya Banerjee, Jr., P. K. Mahanti
Abstract:
A social network is a set of people or organization or other social entities connected by some form of relationships. Analysis of social network broadly elaborates visual and mathematical representation of that relationship. Web can also be considered as a social network. This paper presents an innovative approach to analyze a social network using a variant of existing ant colony optimization algorithm called as Clever Ant Colony Metaphor. Experiments are performed and interesting findings and observations have been inferred based on the proposed model.
Keywords: Social Network, Ant Colony, Maximum Clique, Sub graph, Clever Ant colony.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1984472 Optimum Performance Measures of Interdependent Queuing System with Controllable Arrival Rates
Authors: S. S. Mishra
Abstract:
In this paper, an attempt is made to compute the total optimal cost of interdependent queuing system with controllable arrival rates as an important performance measure of the system. An example of application has also been presented to exhibit the use of the model. Finally, numerical demonstration based on a computing algorithm and variational effects of the model with the help of the graph have also been presented.Keywords: Computing, Controllable arrival rate, Optimum performance measure.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1466471 Performance Comparison and Analysis of Different Schemes and Limiters
Authors: Wang Wen-long, Li Hua, Pan Sha
Abstract:
Eight difference schemes and five limiters are applied to numerical computation of Riemann problem. The resolution of discontinuities of each scheme produced is compared. Numerical dissipation and its estimation are discussed. The result shows that the numerical dissipation of each scheme is vital to improve scheme-s accuracy and stability. MUSCL methodology is an effective approach to increase computational efficiency and resolution. Limiter should be selected appropriately by balancing compressive and diffusive performance.
Keywords: Scheme; Limiter, Numerical simulation, Riemannproblem.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2482470 Block Sorting: A New Characterization and a New Heuristic
Authors: Swapnoneel Roy, Ashok Kumar Thakur, Minhazur Rahman
Abstract:
The Block Sorting problem is to sort a given permutation moving blocks. A block is defined as a substring of the given permutation, which is also a substring of the identity permutation. Block Sorting has been proved to be NP-Hard. Until now two different 2-Approximation algorithms have been presented for block sorting. These are the best known algorithms for Block Sorting till date. In this work we present a different characterization of Block Sorting in terms of a transposition cycle graph. Then we suggest a heuristic, which we show to exhibit a 2-approximation performance guarantee for most permutations.Keywords: Block Sorting, Optical Character Recognition, Genome Rearrangements, Sorting Primitives, ApproximationAlgorithms
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2138469 A Finite-Time Consensus Protocol of the Multi-Agent Systems
Authors: Xin-Lei Feng, Ting-Zhu Huang
Abstract:
According to conjugate gradient algorithm, a new consensus protocol algorithm of discrete-time multi-agent systems is presented, which can achieve finite-time consensus. Finally, a numerical example is given to illustrate our theoretical result.
Keywords: Consensus protocols; Graph theory; Multi-agent systems;Conjugate gradient algorithm; Finite-time.
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 2138468 Tool for Fast Detection of Java Code Snippets
Authors: Tomáš Bublík, Miroslav Virius
Abstract:
This paper presents general results on the Java source code snippet detection problem. We propose the tool which uses graph and subgraph isomorphism detection. A number of solutions for all of these tasks have been proposed in the literature. However, although that all these solutions are really fast, they compare just the constant static trees. Our solution offers to enter an input sample dynamically with the Scripthon language while preserving an acceptable speed. We used several optimizations to achieve very low number of comparisons during the matching algorithm.
Keywords: AST, Java, tree matching, Scripthon, source code recognition
Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 1958