University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 Fr'echet-Like Distances between Two Rooted Trees 1 12 EN Elena Farahbakhsh Touli Stockholm University, Department of Mathematics elena.touli@math.su.se The purpose of this paper is to extend the definition of Fr'echet distance which measures the distance between two curves to a distance (Fr'echet-Like distance) which measures the similarity between two rooted trees.<br />In this paper, I prove that the Fr'echet-Like distance between two trees is SNP-hard to compute.<br /> Later, I modify the definition of Fr'echet-Like distance to measure the distance between two merge trees, and I prove the relation between the interleaving distance and the modified Fr'echet-Like distance. Merge trees,Fr'echet distance,Fr'echet-Like distance,modified Fr'echet-Like distance,interleaving distance https://jac.ut.ac.ir/article_81145.html https://jac.ut.ac.ir/article_81145_9cd801c5f8020bd4f3d182de4877a405.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 \$4\$-total mean cordial labeling of special graphs 13 22 EN R Ponraj Department of Mathematics Sri Parakalyani College Alwarkurichi -627 412, India ponrajmaths@gmail.com S SUBBULAKSHMI Sri Paramakalyani College Alwarkurichi-627412, Tamilnadu, India ssubbulakshmis@gmail.com S Somasundaram Department of Mathematics Manonmaniam sundarnar university, Abishekapatti, Tirunelveli-627012, Tamilnadu, India somutvl@gmail.com Let \$G\$ be a graph. Let \$f:Vleft(Gright)rightarrow left{0,1,2,ldots,k-1right}\$ be a function where \$kin mathbb{N}\$ and \$k>1\$. For each edge \$uv\$, assign the label \$fleft(uvright)=leftlceil frac{fleft(uright)+fleft(vright)}{2}rightrceil\$. \$f\$ is called \$k\$-total mean cordial labeling of \$G\$ if \$left|t_{mf}left(iright)-t_{mf}left(jright) right| leq 1\$, for all \$i,jinleft{0, 1, ldots, k-1right}\$, where \$t_{mf}left(xright)\$ denotes the total number of vertices and edges labelled with \$x\$, \$xinleft{0,1,2,ldots,k-1right}\$. A graph with admit a \$k\$-total mean cordial labeling is called \$k\$-total mean cordial graph. https://jac.ut.ac.ir/article_81169.html https://jac.ut.ac.ir/article_81169_28389b60f46526921271f4681f287da6.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 A New Numerical Solution for System of Linear Equations 23 39 EN Iman Shojaei Align Technology Inc, San Jose, CA 95134, USA shojaei.iman@gmail.com Hossein Rahami 0000-0001-7540-8412 School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran hrahami@ut.ac.ir In this paper we have developed a numerical method for solving system of linear equations through taking advantages of properties of repetitive tridiagonal matrices. <br />A system of linear equations is usually obtained in the final step of many science and engineering problems such as problems involving partial differential equations. <br />In the proposed algorithm, the problem is first solved for repetitive tridiagonal matrices (i.e., system of linear equations) and a closed-from relationship is obtained.<br /> This relationship is then used for solving a general matrix through converting the matrix into a repetitive tridiagonal matrix and a remaining matrix that is moved to the right-hand side of the equation. <br />Therefore, the problem is converted into a repetitive tridiagonal matrix problem where we have a vector of unknowns on the right-hand side (in addition to the left-hand side) of the equation. <br />The problem is solved iteratively by first using an initial guess to define the vector on the right-hand side of the equation and then solving the problem using the closed-from relationship for repetitive tridiagonal matrices. The new obtained solution is then substituted in the right-hand side of the equation and the tridiagonal problem is solved again. <br />This process is carried out iteratively until convergence is achieved. Computational complexity of the method is investigated and efficiency of the method is shown through several examples. <br />As indicated in the examples, one of the advantages of the proposed method is its high rate of convergence in problems where the given matrix includes large off-diagonal entries. <br />In such problems, methods like Jacobi, Gauss-Seidel, and Successive Over-Relaxation will either have a low rate of convergence or be unable to converge. https://jac.ut.ac.ir/article_81267.html https://jac.ut.ac.ir/article_81267_23db04a9319ce7c9f6bbf2eb577623b4.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 \$alpha\$-Gap Greedy Spanner 41 60 EN Hosein Salami Department of Computer Engineering, Ferdowsi University of Mashhad hossein.salami@mail.um.ac.ir Mostafa Nouri Baygi Department of Computer Engineering, Ferdowsi University of Mashhad, Mashhad, Iran nouribaygi@um.ac.ir In this paper, we have introduced a new geometric spanner called \$alpha\$-Gap greedy spanner, which is a parametric approximation of the well-known Gap-greedy spanner. We will show theoretically and experimentally that this spanner is similar to the Gap-greedy spanner in terms of qualitative features such as weight and maximum degree of vertices. %Wehave shown that this spanner can be computed in \$O(n^2 log n)\$ time with\$O(n)\$ space, and \$O(n log n)\$ expected time on the set of points placedrandomly in a unit square.<br />Two algorithms have been proposed with running time \$O(n^2 log n)\$ for constructing the \$alpha\$-Gap greedy spanner. Space complexity of the first algorithm is \$O(n^2)\$, but it is reduced to \$O(n)\$ in the second one. <br />%The proposed algorithms have a parameter, called \$alpha\$, by which the similarity of the \$alpha\$-Gap greedy spanner to the Gap-greedy spanner, in terms of quality features mentioned above, can be determined. <br />Also, we have shown on the points placed randomly in a unit square, the \$alpha\$-Gap greedy spanner can be constructed in the expected \$O(n log n)\$ time. computational geometry,geometric spanners,gap greedy spanner,construction algorithms,algorithm complexity https://jac.ut.ac.ir/article_81307.html https://jac.ut.ac.ir/article_81307_669c0a0df2c0484e4332a6e5ff9041b6.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 Signature GOA: A novel comfort zone parameter adjustment using fuzzy signature for task scheduling in cloud environment 61 95 EN Aboozar Zandvakili Department of Computer Science, Shahid Bahonar University of Kerman, Kerman, Iran zandvakili.a@gmail.com Najme Mansouri Department of Computer science, Shahid Bahonar University of Kerman, Kerman, Iran najme.mansouri@gmail.com Mohammad Masoud Javidi Department of Computer Science, Shahid Bahonar University of Kerman, Kerman, Iran javidi@uk.ac.ir Task scheduling in cloud computing plays an essential role for service provider to enhance its quality of service. Grasshopper Optimization Algorithm (GOA) is an evolutionary computation technique developed by emulating the swarming behavior of grasshoppers while searching for food. GOA is easy to implement but it cannot make full utilization of every iteration, and there is a risk of falling into the local optimal. This paper proposes a suitable approach for adjusting the comfort zone parameter based on the fuzzy signatures called signature GOA (SGOA) to balance exploration and exploitation. Then, we propose task scheduling based on SGOA by considering different objectives such as completion time, delay, and the load balancing on the machines. Finally, different algorithms such as Particle Swarm Optimization (PSO), Simulated Annealing (SA), Tabu Search (TS), and multi-objective genetic algorithm, are used for comparison. The results show that among all algorithms, SGOA can be successful in much less iteration. Task scheduling,Fuzzy signature,Multi-objective optimization https://jac.ut.ac.ir/article_81539.html https://jac.ut.ac.ir/article_81539_ce78841b3d8f6d59f9c7a49f7119ff28.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 A Numerical Method for Eigensolution of Tridiagonal Matrices 97 115 EN Iman Shojaei Align Technology Inc, San Jose, CA 95134, USA shojaei.iman@gmail.com Hossein Rahami 0000-0001-7540-8412 School of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran hrahami@ut.ac.ir In this paper we have developed an iterative method to solve eigenproblem for non-repetitive tridiagonal matrices. The importance of eigensolution for tridiagonal matrices is that in many algorithms the eigneproblem for an arbitrary matrix is first converted to the eigenproblem for a tridiagonal matrix and then the problem is tackled. Our proposed method was developed through taking advantages of some unique properties of repetitive and non-repetitive tridiagonal matrices. First, we established closed-form solutions for the system of linear equations \$ bf{Mx=f} \$  for the condition \$ mathbf{M} \$ is tridiagonal. When \$ mathbf{M} \$ is a repetitive tridiagonal matrix, the unknown vector \$ mathbf{x} \$, the vector \$ mathbf{f} \$, and the coefficient matrix \$ mathbf{M} \$ are expanded using orthogonal basis of matrix \$ mathbf{M} \$ and closed-form relationships are obtained. For non-repetitive matrix \$ mathbf{M} \$, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then using orthogonal basis of matrix \$ mathbf{M} \$ and closed-form relationships are obtained. For non-repetitive matrix \$ mathbf{M} \$, the tridiagonal matrix algorithm is used to efficiently solve the matrix equation. We then implemented these solutions in an iterative relationship for eigenproblem where eigenpairs of non-repetitive tridiagonal matrices were obtained through successive solution of the tridiagonal matrix equation efficiently solved above. Furthermore, closed-form relationships for eigenpairs of repetitive tridiagonal matrices were implemented in the algorithm as start point for eigensolution of non-repetitive tridiagonal matrices so that the required number of iterations was significantly reduced. Computational complexity of the proposed method is \$ O(n^2) \$ that is competitive with the best existing algorithms in literature. As indicated through several numerical examples, the advantages of the proposed algorithm include high rate of convergence, computational efficiency in each iteration, simple implementation, and availability of an objective start point for initialization.  iterative method,eigensolution,repetitive tridiagonal matrices,non-repetitive tridiagonal matrices,Efficient Solution,system of linear equations https://jac.ut.ac.ir/article_81543.html https://jac.ut.ac.ir/article_81543_f245166d44046556266d8232c4fde63b.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 An Alternative Proof for a Theorem of R.L. Graham Concerning CHEBYSHEV Polynomials 117 122 EN A.M.S.. Ramasamy Department of Mathematics, Pondicherry University, Pondicherry, India amsramasamy@gmail.com R Ponraj Department of Mathematics Sri Parakalyani College Alwarkurichi -627 412, India ponrajmaths@gmail.com In this paper, an alternative proof is provided for a theorem of R.L.Graham concerning Chebyshev polynomials.  While studying the properties of a double star, R.L.Graham  proved a theorem concerning Chebyshev polynomials of the first kind \${T_n (x)}\$. The purpose of this paper is to provide an alternative proof for his theorem. Our method is based on the divisibility properties of the natural numbers. One may observe that the Chebyshev polynomials evaluated at integers considered by R.L.Graham match with the solutions of the Pell's equation for a general, square-free \$D in N\$. Chebyshev polynomials,Pell's equation,prime factorization https://jac.ut.ac.ir/article_81593.html https://jac.ut.ac.ir/article_81593_93d781a6ea7bffe6615c83f4372cea32.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 On the Minimum of True Matches in Exact Graph Matching with Simulated Annealing 123 134 EN Hashem Ezzati Department of Computer Science, Amir Kabir University of Technology, Tehran, Iran h.ezzati@aut.ac.ir Mahmood Amintoosi Faculty of Mathematics and Computer science, Hakim Sabzevari University, Sabzevar, Iran m.amintoosi@hsu.ac.ir Hashem Tabasi Department of Computer Science, Damghan University tabasi@du.ac.ir Graph matching is one of the most important problems in graph theory and combinatorial optimization, with many applications in various domains. Although meta-heuristic algorithms have had good performance on many NP-Hard and NP-Complete problems, but for graph matching problem, there were not reported superior solutions by these sort of algorithms. The reason of this inefficiency  has not been investigated yet. In this paper it has been shown that Simulated Annealing (SA) as an instance of a meta-heuristic method is unlikely to be even close to the optimal solution for this problem. Mathematical and experimental results showed that the chance to reach to a partial solution, is very low, even for small number of true matches. In addition to theoretical discussion, the experimental results also verified our idea; for example, in two sample graphs with \$10000\$ vertices, the probability of reaching to a solution with at least three correct matches is about \$0.02\$ with simulated annealing. Graph matching,Simulated Annealing,Meta-heuristic,Stochastic Optimization https://jac.ut.ac.ir/article_81628.html https://jac.ut.ac.ir/article_81628_c4ff6be4c01880d61752828a09af50ca.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 A fast algorithm for the linear programming problem constrained with the Weighted power mean -- Fuzzy Relational Equalities (WPM-FRE) 135 148 EN Amin Ghodousian Faculty of Engineering Science, College of Engineering, University of Tehran, P.O.Box 11365-4563, Tehran, Iran. a.ghodousian@ut.ac.ir Sara Zal University of Tehran, Department of Algorithms and Computation sarazl1392@gmail.com In this paper, a linear programming problem is investigated in which the feasible region is formed as a special type of fuzzy relational equalities (FRE). In this type of FRE, fuzzy composition is considered as the weighted power mean operator (WPM). Some theoretical properties of the feasible region are derived and some necessary and sufficient conditions are also presented to determine the feasibility of the problem. Moreover, two procedures are proposed for simplifying the problem. Based on some structural properties of the problem, an algorithm is presented to find the optimal solutions and finally, an example is described to illustrate the algorithm.  Fuzzy relational equalities,mean operators,weighted power mean,fuzzy compositions,Linear programming https://jac.ut.ac.ir/article_81633.html https://jac.ut.ac.ir/article_81633_88056bc54e924723d34598521ee1c6ad.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 Pair Difference Cordiality of Some Snake and Butterfly Graphs 149 163 EN R Ponraj Department of Mathematics Sri Parakalyani College Alwarkurichi -627 412, India ponrajmaths@gmail.com A Gayathri Research Scholor,Reg.No:20124012092023 Department of Mathematics Manonmaniam Sundaranar University, Abhishekapati,Tirunelveli&ndash;627 012, India gayugayathria555@gmail.com S Somasundaram Department of Mathematics Manonmaniam sundarnar university, Abishekapatti, Tirunelveli-627012, Tamilnadu, India somutvl@gmail.com noindent Let \$G = (V, E)\$ be a \$(p,q)\$ graph.\<br />Define begin{equation*}<br />rho =<br />begin{cases}<br />frac{p}{2} ,& text{if \$p\$ is even}\<br />frac{p-1}{2} ,& text{if \$p\$ is odd}\<br />end{cases}<br />end{equation*}\ <br /> and \$L = {pm1 ,pm2, pm3 , cdots ,pmrho}\$ called the set of labels.\<br />noindent Consider a mapping \$f : V longrightarrow L\$ by assigning different labels in L to the different elements of V when p is even and different labels in L to p-1 elements of V and repeating a label for the remaining one vertex when \$p\$ is odd.The labeling as defined above is said to be a pair difference cordial labeling if for each edge \$uv\$ of \$G\$ there exists a labeling \$left|f(u) - f(v)right|\$ such that \$left|Delta_{f_1} - Delta_{f_1^c}right| leq 1\$, where \$Delta_{f_1}\$ and \$Delta_{f_1^c}\$ respectively denote the number of edges labeled with \$1\$ and number of edges not labeled with \$1\$. A graph \$G\$ for which there exists a pair difference cordial labeling is called a pair difference cordial graph. In this paper we investigate the pair difference cordial labeling behavior of some snake and butterfly graphs. Triangular snake,Alternate triangular snake,Quadrilatral Snake,Alternate Quadrilatral Snake,Butter fly https://jac.ut.ac.ir/article_81649.html https://jac.ut.ac.ir/article_81649_9670058e7708586f959c57de1e3434f5.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 Use of Digital Image Watermarking to Enhance the Security of Graphical Password Authentication 165 180 EN Saeid Sadeghi Department of computer engineering, Islamic azad unievrsity (central branch), Tehran, Iran saeid.sadeghi71@gmail.com Kooroush Manochehri Department of computer engineering, Amirkabir university of Technology, Tehran, Iran kmanochehri@aut.ac.ir mohsen jahanshahi Department of Computer Engineering.Software, Islamic Azad University, Central Tehran Branch, Tehran,Iran mjahanshahi@iauctb.ac.ir There are several techniques for implement an authentication system for computers that most commonly use the clear text password. One of the security problems is the use of a text password, the lack of choosing a complicated password by users due to forgetting, and being guessable and retrieved by attackers. One of the methods for passing text passwords is the use of graphical password authentication systems that increase the amount of forgetting passwords by using images instead of text characters. In this paper, the security challenges of using a graphical password are discussed. Then, explain a method for using the watermarking digital image for the authentication process and providing an algorithm suitable for watermarking and enhance the security of graphical password authentication system, and its quantitative and qualitative security parameters will be examined. Digital Image,Watermarking,Graphical Password,Computer Security,authentication https://jac.ut.ac.ir/article_81653.html https://jac.ut.ac.ir/article_81653_959c8a5c4847c14b289e7956c5168e4c.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 A Survey on Tenacity Parameter\Part I 181 196 EN Asieh Khoshnood University of Tehran Department of Algorihthms and Computation, Tehran, Iran asieh.khoshnood@ut.ac.ir Dara Moazzami University of Tehran, College of Engineering, Department of Engineering Science dmoazzami@ut.ac.ir If we think of the graph as modeling a network, the vulnerability measure<br />the resistance of the network to disruption of operation after the failure of certain<br />stations or communication links. In assessing the "vulnerability"<br />of a graph one determines the extent to which the graph retains certain<br />properties after the removal of vertices and / or edges. Many graph theoretical parameters have been used to describe the vulnerability of communication networks, including connectivity, integrity, toughness, binding number, tenacity and... .<br /> In this paper we survey and discuss tenacity and its properties in vulnerability calculation and we will compare<br />different measures of vulnerability with tenacity for several classes of<br />graphs. Vulnerability,Tenacity,connectivity,Integrity,toughness,binding number https://jac.ut.ac.ir/article_81721.html https://jac.ut.ac.ir/article_81721_76913d1142ab4fde5d94bd79b545853f.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 53 1 2021 06 01 BloomEclat: Efficient Eclat Algorithm based on Bloom filter 197 208 EN sina abbasi Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Iran sina.abbasi.415@ut.ac.ir Ali Moieni Department of Algorithms and Computation, School of Engineering Science, College of Engineering, University of Tehran, Iran. moeini@ut.ac.ir Eclat is an algorithm that finds frequent itemsets. It uses a vertical database and calculates item's support by intersecting transactions. However, Eclat suffers from the exponential time complexity of calculating the intersection of transactions. In this paper, a randomized algorithm called BloomEclat based on Bloom filter is presented to improve the Eclat algorithm complexity in finding frequent itemsets. Through Bloom Filter, an element’s membership to a set, can be checked and set operations such as intersection and union of two sets can be executed in a time efficient manner. By using these capabilities, Eclat algorithm’s intersecting problem can significantly improve. In BloomEclat algorithm with slight false positive error, the speed of the intersecting transactions is increased, and consequently the execution time is reduced. Eclat algorithm,bloom filter,frequent pattern mining,association rules mining,Data Mining,Union,Intersection https://jac.ut.ac.ir/article_81890.html https://jac.ut.ac.ir/article_81890_5bda386b4320351819ad7b35d79c0bd8.pdf