University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 PD-prime cordial labeling of graphs 1 7 EN R Ponraj Department of Mathematics Sri Parakalyani College Alwarkurichi -627 412, India ponrajmaths@gmail.com S SUBBULAKSHMI Research Scholar, Department of Mathematics 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 vspace{0.2cm}<br /> Let \$G\$ be a graph and \$f:V(G)rightarrow {1,2,3,.....left|V(G)right|}\$ be a bijection. Let \$p_{uv}=f(u)f(v)\$ and\ <br /> \$ d_{uv}=<br /> begin{cases}<br /> left[frac{f(u)}{f(v)}right] ~~if~~ f(u) geq f(v)\ \<br /> left[frac{f(v)}{f(u)}right] ~~if~~ f(v) geq f(u)\ <br /> end{cases}<br /> \$\<br /> for all edge \$uv in E(G)\$. For each edge \$uv\$ assign the label \$1\$ if \$gcd (p_{uv}, d_{uv})=1\$ or \$0\$ otherwise. \$f\$ is called PD-prime cordial labeling if \$left|e_{f}left(0right)-e_{f}left(1right) right| leq 1\$ where \$e_{f}left(0right)\$ and \$e_{f}left(1right)\$ respectively denote the number of edges labelled with \$0\$ and \$1\$. A graph with admit a PD-prime cordial labeling is called PD-prime cordial graph.<br /> & & vspace{0.2cm} Path,Bistar,subdivison of star,subdivison of bistar,Wheel,Fan,double fan https://jac.ut.ac.ir/article_75109.html https://jac.ut.ac.ir/article_75109_617cbbcab35443d18a0bffd29ccc4cb6.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Fr{'e}chet and Hausdorff Queries on \$x\$-Monotone Trajectories 9 17 EN Zeinab Saeidi Yazd University, Iran zsaeidi2007@gmail.com Mohammad Farshi 0000-0002-1986-2722 Department of Mathematical Sciences, Yazd University, Yazd, Iran mfarshi@yazd.ac.ir vspace{0.2cm}<br />In this paper, we design a data structure for the following problem. Let \$pi\$ be an \$x\$-monotone trajectory with \$n\$ vertices in the plane and \$epsilon >0\$. We show how to preprocess \$pi\$ and \$epsilon\$ into a data structure such that for any horizontal query segment \$Q\$ in the plane, one can quickly determine the minimal continuous fraction of \$pi\$ whose Fr{'e}chet and Hausdorff distance to the horizontal query segment \$Q\$ is at most some threshold value \$epsilon\$. We present a data structure for this query that needs \$mathcal{O}(nlog{}n)\$ preprocessing time, \$mathcal{O}(n)\$ space, and \$mathcal{O}(log{} n)\$ query time. & & vspace{0.2cm} Distance https://jac.ut.ac.ir/article_75110.html https://jac.ut.ac.ir/article_75110_4e3b3a30f827f265419f1d3ad7b9e08d.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 On the max - ``Fuzzy Or'' composition fuzzy inequalities systems 19 34 EN Amin Ghodousian University of Tehran, College of Engineering, Faculty of Engineering Science a.ghodousian@ut.ac.ir Ali Babalhavaeji Department of Algorithms and Computation, University of Tehran, Tehran, Iran ali.babalhavaeji@ut.ac.ir Elnaz Bashir Department of Algorithms and Computation, University of Tehran, Tehran, Iran elnaz.bashir@yahoo.com Fuzzy relation,fuzzy relational inequality,fuzzy compositions and fuzzy averaging operator https://jac.ut.ac.ir/article_75139.html https://jac.ut.ac.ir/article_75139_f59a9e30545f3f2b3c967cd68211d644.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 A generalization of zero-divisor graphs 35 45 EN Peyman Nasehpour 0000-0001-6625-364X Department of Engineering Science, Golpayegan University of Technology, Golpayegan, Iran nasehpour@gmail.com In this paper, we introduce a family of graphs which is a generalization of zero-divisor graphs and compute an upper-bound for the diameter of such graphs. We also investigate their cycles and cores Zero-divisor graphs,diameter,Core,cycle,semigroups,semimodule https://jac.ut.ac.ir/article_75141.html https://jac.ut.ac.ir/article_75141_8a05c25a3bf4b424370dde1982daf081.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Efficient Approximation Algorithms for Point-set Diameter in Higher Dimensions 47 61 EN Mahdi Imanparast Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran m.imanparast@ub.ac.ir Seyed Naser Hashemi Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran nhashemi@aut.ac.ir Ali Mohades Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran mohaddes@aut.ac.ir We study the problem of computing the diameter of a  set of \$n\$ points in \$d\$-dimensional Euclidean space for a fixed dimension \$d\$, and propose a new \$(1+varepsilon)\$-approximation algorithm with \$O(n+ 1/varepsilon^{d-1})\$ time and \$O(n)\$ space, where \$0 < varepsilonleqslant 1\$. We also show that the proposed algorithm can be modified to a \$(1+O(varepsilon))\$-approximation algorithm with \$O(n+ 1/varepsilon^{frac{2d}{3}-frac{1}{2}})\$ running time. Our proposed algorithms are different with the previous algorithms in terms of computational technique and data structures. These results provide some improvements in comparison with existing algorithms in terms of simplicity and data structure. diameter,Point-set,Approximation algorithms,Higher dimensions https://jac.ut.ac.ir/article_75162.html https://jac.ut.ac.ir/article_75162_b7dd1282a7b33bb86cf9ad24b567cbc9.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 On the outer-connected reinforcement and bondage problems in bipartite graphs: the algorithmic complexity 63 74 EN Maliheh Hashemipour Department of Computer Science, Yazd University, Yazd, Iran. mhashemi@stu.yazd.ac.ir Mohammadreza Hooshmandasl 0000-0002-3834-3610 Department of Computer Science, Yazd University, Yazd, Iran. hooshmandasl@yazd.ac.ir Ali Shakiba 0000-0002-2253-1166 Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran. ali.shakiba@vru.ac.ir An outer connected dominating(OCD) set of a graph \$G=(V,E)\$ is a set \$tilde{D} subseteq V\$ such that every vertex not in \$S\$ is adjacent to a vertex in \$S\$, and the induced subgraph of \$G\$ by \$V setminus tilde{D}\$, i.e. \$G [V setminus tilde{D}]\$, is connected. The OCD number of \$G\$ is the smallest cardinality of an OCD set of \$G\$. The outer-connected bondage number of a nonempty graph G is the smallest number of edges whose removal from G results in a graph with a larger OCD number. Also, the outer-connected reinforcement number of G is the smallest number of edges whose addition to G results in a graph with a smaller OCD number. In 2018, Hashemi et al. demonstrated that the decision problems for the Outer-Connected Bondage and the Outer-Connected Reinforcement numbers are all NP-hard in general graphs. In this paper, we improve these results and show their hardness for bipartite graphs. Also, we obtain bounds for the outer-connected bondage number. Bipartite graphs,Outer-connected domination,Bondage,Reinforcement,Complexity https://jac.ut.ac.ir/article_75163.html https://jac.ut.ac.ir/article_75163_c7f2647cd3f4052bf5fc70307cdf0272.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Maximum Zagreb Indices Among All \$p-\$Quasi \$k-\$Cyclic Graphs 75 82 EN Ali Reza Ashrafi University of Kashan ashrafi_1385@yahoo.co.in Ali Ghalavand University of Kashan ali797ghalavand@gmail.com vspace{0.2cm}<br />Suppose \$G\$ is a simple and connected graph. The first and second Zagreb indices of \$G\$ are two degree-based graph invariants defined as \$M_1(G) = sum_{v in V(G)}deg(v)^2\$ and \$M_2(G) = sum_{e=uv in E(G)}deg(u)deg(v)\$, respectively. The graph \$G\$ is called \$p-\$quasi \$k-\$cyclic, if there exists a subset \$S\$ of vertices such that \$|S| = p\$, \$G setminus S\$ is \$k-\$cyclic and there is no a subset \$S^prime\$ of \$V(G)\$ such that \$|S^prime| < |S|\$ and \$G setminus S^prime\$ is \$k-\$cyclic. The aim of this paper is to characterize all graphs with maximum values of Zagreb indices among all \$p-\$quasi \$k-\$cyclic graphs with \$k leq 3\$. & & vspace{0.2cm} \$p-\$quasi \$k-\$cyclic graph,first Zagreb index,second Zagreb index,cyclomatic number,k-cyclic graph https://jac.ut.ac.ir/article_75164.html https://jac.ut.ac.ir/article_75164_5629cec8c1befcde57ffd7146fa1be6c.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Eye Tracking for Autism Disorder Analysis using Image Processing 83 98 EN Zohre Kiapasha Department of Information Technology Engineering, Mazandaran University of Science and Technology, Babol, Iran ze.kiapasha@yahoo.com Iraj Mahdavi Department of Industrial Engineering, School of Engineering, Damghan University, Damghan, Iran irajarash@rediffmail.com Hamed Fazlollahtabar Department of Industrial Engineering, School of Engineering, Damghan University, Damghan, Iran hfazl@iust.ac.ir Zahra Kiapasha Department of Mathematical Sciences, University of Mazandaran, Babolsar, Iran z.kiapasha@yahoo.com Analyzing eyes performance is essential for effective functioning of human. Therefore, following their motion could help doctors to make quick and accurate diagnoses for disorders like Autism, schizophrenia, or attention deficit hyperactivity disorder. Recently, several studies investigated autism disorder diagnosis and treatment. Meanwhile, various algorithms have been provided for eye tracking. In this paper, it is intended to identify diagnosis parameters of autism disorder using eye tracking concept. The eye tracking algorithm that has been used in this research is simple and sufficient accurate to appropriate function on videos with varying quality. The direct analysis of gaze and study of the interactions of its features are employed a useful method for diagnosis of autism. For this purpose, two separate groups of ordinary children and children with autism are considered. By tracking their eyes while watching television and performing the necessary analyses then their eye movements are compared and discussed. To identify pupils is face detection Viola Jones algorithm is implemented. Autism disorder,eye tracking,image processing,Clustering https://jac.ut.ac.ir/article_75178.html https://jac.ut.ac.ir/article_75178_4508d98f9a009f3963bab38d66254251.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Minimum Spanning Tree of Imprecise Points Under \$L_1\$-metric 99 110 EN Amir Mesrikhani Yazd university mesrikhani@gmail.com Mohammad Farshi Department of Computer Science, Yazd University, Yazd, Iran m.farshi@gmail.com Behnam Iranfar Department of Computer Science, Yazd University, Yazd, Iran biranfar@gmail.com Let \$S\$ be a set of imprecise points that is represented by axis-aligned pairwise disjoint squares in the plane. A precise instance of \$S\$ is a set of points, one from each region of \$S\$. In this paper, we study the optimal minimum spanning tree (textit{OptMST}) problem on \$S\$. The textit{OptMST} problem looks for the precise instance of \$S\$ such that the weight of the MST in this instance, maximize (Max-MST) or minimize (Min-MST) between all precise instances of~\$S\$ under \$L_1\$-metric. We present a \$(frac{3}{7})\$-approximation algorithm for Max-MST. This is an improvement on the best-known approximation factor of \$1/3\$. If \$S\$ satisfies \$k\$-separability property (the distance between any pair of squares are at least \$k.a_{max}\$ where \$a_{max}\$ is the maximum length of the squares), the factor parameterizes to \$frac{2k+3}{2k+7}\$. We propose a new lower bound for Min-MST problem on \$S\$ under \$L_1\$-metric where \$S\$ contains unit squares and provide an approximation algorithm with \$(1+2sqrt{2})\$ asymptotic factor. Minimum Spanning tree,Imprecise point set,Approximation algorithm https://jac.ut.ac.ir/article_75187.html https://jac.ut.ac.ir/article_75187_f9c4f22d395c7caa9a536f7440667dde.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Xerus Optimization Algorithm (XOA): a novel nature-inspired metaheuristic algorithm for solving global optimization problems 111 126 EN Farnood Samie Yousefi Faculty of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran. f.samieyousefi@ut.ac.ir Noushin Karimian Faculty of Engineering Science, College of Engineering, University of Tehran, Tehran, Iran. nkarimian@ut.ac.ir Amin Ghodousian University of Tehran, College of Engineering, Faculty of Engineering Science a.ghodousian@ut.ac.ir Over the recent years, many research has been carried out on applying the optimization approach to science and engineering problems. Thereby, numerous metaheuristic algorithms have been developed for solving such type of challenge. Despite an increase in the number of these algorithms, there is currently no specific algorithm which can be employed to optimize all varieties of problems. In the current research, a novel metaheuristic algorithm for global and continuous nonlinear optimization, named as Xerus Optimization Algorithm (XOA) has been introduced. XOA has been inspired by group living and lifestyle of cape ground squirrels (Xerus inauris), by taking into account their co-operation in living together, hunting, and communication, etc. In order to evaluate the efficiency of XOA, algorithms for 30 different benchmarks have been analyzed and compared to some novel and renowned metaheuristic algorithms. The simulation response illustrates a significant improvement in  the performance of the novel XOA, in comparison to the algorithms presented in the literature. The proposed algorithm can be employed for many applications that require a solution to different optimization problems. Xerus Optimization Algorithm,Global Optimization,Evolutionary algorithms,Metaheuristic algorithms https://jac.ut.ac.ir/article_75188.html https://jac.ut.ac.ir/article_75188_bbceddde3a611eed1a3cee0faf27a323.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 Tenacious Graph is NP-hard 127 134 EN Dara Moazzami Department of Algorithms and Computation, Faculty of Engineering Science, College of Engineering, University of Tehran, Iran, dmoazzami@ut.ac.ir The tenacity of a graph \$G\$, \$T(G)\$, is defined by<br />\$T(G) = min{frac{mid Smid +tau(G-S)}{omega(G-S)}}\$, where the<br />minimum is taken over all vertex cutsets \$S\$ of \$G\$. We define<br />\$tau(G - S)\$ to be the number of the vertices in the largest<br />component of the graph \$G-S\$, and \$omega(G-S)\$ be the number of<br />components of \$G-S\$. In this paper<br />we consider the relationship between the minimum degree \$delta (G)\$ of a graph and the complexity<br />of recognizing if a graph is \$T\$-tenacious. Let \$Tgeq 1\$ be a rational number. We first show that if<br />\$delta(G)geq frac{Tn}{T+1}\$, then \$G\$ is \$T\$-tenacious. On the other hand, for any fixed \$epsilon>0\$, we<br />show that it is \$NP\$-hard to determine if \$G\$ is \$T\$-tenacious, even for the class of graphs with \$delta(G)geq<br />(frac{T}{T+1}-epsilon )n\$. minimum degree,Complexity,Tenacity,\$NP\$-hard,\$T\$-tenacious https://jac.ut.ac.ir/article_75276.html https://jac.ut.ac.ir/article_75276_859179202bd0083eec05d9bf12027118.pdf
University of Tehran Journal of Algorithms and Computation 2476-2776 2476-2784 51 2 2019 12 01 A Review of Replica Replacement Techniques in Grid Computing and Cloud Computing 134 151 EN 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@mail.uk.ac.ir A data-intensive computing platform, encountered in some grid and cloud computing applications, includes numerous tasks that process, transfer or analysis large data files. In such environments, there are large and geographically distributed users that need these huge data. Data management is one of the main challenges of distributed computing environment since data plays on devoted role. Dynamic data replication techniques have been widely applied to improve data access and availability. In order to introduce an appropriate data replication algorithm, there are four important problems that must be solved. 1) Which file should be replicated; 2) How many suitable new replicas should be stored; 3) Where the new replicas should be placed; 4) Which replica should be deleted to make room for new copies. In this paper, we focus particularly on replica replacement issue which makes a significant difference in the efficiency of replication algorithm. We survey replica replacement approaches (from 2004 to 2018) that are developed for both grid and cloud environments. The presented review illustrates the replica replacement problem from a technological and it differs significantly from previous reviews in terms of comprehensiveness and integrated discussion. In this paper, we present different parameters involved in replacement process and show the key points of the recent algorithms with a tabular representation of all those factors. We also report open issues and new challenges in the area. Cloud Computing,Grid,Replica replacement,File popularity,simulation https://jac.ut.ac.ir/article_75291.html https://jac.ut.ac.ir/article_75291_ad3990d41a21be0b98deac827518d8fb.pdf