University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
$Z_k$-Magic Labeling of Some Families of Graphs
1
12
EN
P.
Jeyanthi
Principal and Head of the Research Centre,Department of Mathematics,Govindammal Aditanar College for Women,Tiruchendur,Tamilnadu,INDIA
jeyajeyanthi@rediffmail.com
K.
Jeyadaisy
Department of Mathematics
Holy Cross College, Nagercoil, Tamilnadu, India.
jeyadaisy@yahoo.com
10.22059/jac.2018.69046
For any non-trivial abelian group A under addition a graph $G$ is said to be $A$-\textit{magic} if there exists a labeling $f:E(G) \rightarrow A-\{0\}$ such that, the vertex labeling $f^+$ defined as $f^+(v) = \sum f(uv)$ taken over all edges $uv$ incident at $v$ is a constant. An $A$-\textit{magic} graph $G$ is said to be $Z_k$-magic graph if the group $A$ is $Z_k$ the group of integers modulo $k$. These $Z_k$-magic graphs are referred to as $k$-\textit{magic} graphs. In this paper we prove that the total graph, flower graph, generalized prism graph, closed helm graph, lotus inside a circle graph, $G\odot\overline{K_m}$, $m$-splitting graph of a path and $m$-shadow graph of a path are $Z_k$-magic graphs.
A-magic labeling,$Z_k$-magic labeling,$Z_k$-magic graph,total graph,flower graph,generalized prism graph,closed helm graph,lotus inside a circle graph,$Godotoverline{K_m}$,$m$-splitting graph,$m$-shadow graph
https://jac.ut.ac.ir/article_69046.html
https://jac.ut.ac.ir/article_69046_6280f6ffe52fb49581c3603a8b60a45f.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Linear programming on SS-fuzzy inequality constrained problems
13
36
EN
Amin
Ghodousian
0000-0002-9224-8470
University of Tehran, College of Engineering, Faculty of Engineering Science
a.ghodousian@ut.ac.ir
shahrzad
oveisi
Department of Algorithms and Computation, University of Tehran,Tehran, Iran.
shahrzad.oveisi@gmail.com
10.22059/jac.2018.69466
In this paper, a linear optimization problem is investigated whose constraints are defined with fuzzy relational inequality. These constraints are formed as the intersection of two inequality fuzzy systems and Schweizer-Sklar family of t-norms. Schweizer-Sklar family of t-norms is a parametric family of continuous t-norms, which covers the whole spectrum of t-norms when the parameter is changed from zero to infinity. Firstly, we investigate the resolution of the feasible region of the problem and studysome theoretical results. A necessary and sufficient condition and three other necessary conditions are derived for determining the feasibility. Moreover, in order to simplify the problem, some procedures are presented. It is proved that the optimal solution of the problem is always resulted from the unique maximum solution and a minimal solution of the feasible region. A method is proposed to generate random feasible max-Schweizer-Sklar fuzzy relational inequalities and an algorithm is presented to solve the problem. Finally, an example is described to illustrate these algorithms.
Fuzzy relation,fuzzy relational inequality,linear optimization,fuzzy compositions and t-norms
https://jac.ut.ac.ir/article_69466.html
https://jac.ut.ac.ir/article_69466_597a69e191920561fefb09353557c2f2.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Snakes and Caterpillars in Graceful Graphs
37
47
EN
Christian
Barrientos
Department of Mathematics, Valencia College, Orlando, FL, 32825, USA.
chr_barrientos@yahoo.com
Sarah
M
Minion
Department of Mathematics, Valencia College, Orlando, FL, 32825, USA
sarah.m.minion@gmail.com
10.22059/jac.2018.69503
Graceful labelings use a prominent place among difference vertex labelings. In this work we present new families of graceful graphs all of them obtained applying a general substitution result. This substitution is applied here to replace some paths with some trees with a more complex structures. Two caterpillars with the same size are said to be \textit{analogous} if the<br />larger stable sets, in both caterpillars, have the same cardinality. We study<br />the conditions that allow us to replace, within a gracefully labeled graph,<br />some snakes (or paths) by analogous caterpillars, to produce a new graceful<br />graph. We present five families of graphs where this replacement is<br />feasible, generalizing in this way some existing results: subdivided trees, first attachment trees, path-like trees, two-point union of paths, and armed crowns.
\a-labeling,graceful labeling,snake,caterpillar. & & \\ %\vspace{0.1cm} \end{tabular}
https://jac.ut.ac.ir/article_69503.html
https://jac.ut.ac.ir/article_69503_bd9e68d1fedd8b959976b68013ae5357.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
$4$-Total prime cordial labeling of some cycle related graphs
49
57
EN
R
Ponraj
Department of Mathematics
Sri Parakalyani College
Alwarkurichi -627 412, India
ponrajmaths@gmail.com
J
Maruthamani
Research Scholar, Register number: 18124012091054, Department of Mathematics, Manonmaniam sundarnar university, Abishekapatti, Tirunelveli-627012, Tamilnadu, India
mmani2011@gmail.com
10.22059/jac.2018.69777
Let $G$ be a $(p,q)$ graph. Let $f:V(G)\to\{1,2, \ldots, k\}$ be a map where $k \in \mathbb{N}$ and $k>1$. For each edge $uv$, assign the label $\gcd(f(u),f(v))$. $f$ is called $k$-Total prime cordial labeling of $G$ if $\left|t_{f}(i)-t_{f}(j)\right|\leq 1$, $i,j \in \{1,2, \cdots,k\}$ where $t_{f}(x)$ denotes the total number of vertices and the edges labelled with $x$. A graph with a $k$-total prime cordial labeling is called $k$-total prime cordial graph. In this paper we investigate the $4$-total prime cordial labeling of some graphs like Prism, Helm, Dumbbell graph, Sun flower graph.
Prism,Helm,Dumbbell graph,Sun flower graph
https://jac.ut.ac.ir/article_69777.html
https://jac.ut.ac.ir/article_69777_b697bb2042469a4545ccaf731813c86a.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
LP problems constrained with D-FRIs
59
79
EN
A.
Ghodousian
0000-0002-9224-8470
Faculty of Engineering Science, College of Engineering, University of Tehran, P.O. Box 11365-4563, Tehran, Iran
a.ghodousian@ut.ac.ir
M.
Jafarpour
0000-0001-7266-5018
University of Tehran, College of Engineering, Faculty of Engineerng Science, Department of Algorithms and Computation
m.jafarpour@ut.ac.ir
10.22059/jac.2018.69778
In this paper, optimization of a linear objective function with fuzzy relational inequality constraints is investigated where the feasible region is formed as the intersection of two inequality fuzzy systems and Dombi family of t-norms is considered as fuzzy composition. Dombi family of t-norms includes a parametric family of continuous strict t-norms, whose members are increasing functions of the parameter. This family of t-norms covers the whole spectrum of t-norms when the parameter is changed from zero to infinity. The resolution of the feasible region of the problem is firstly investigated when it is defined with max-Dombi composition. Based on some theoretical results, a necessary and sufficient condition and three other necessary conditions are derived for determining the feasibility. Moreover, in order to simplify the problem, some procedures are presented. It is shown that a lower bound is always attainable for the optimal objective value. Also, it is proved that the optimal solution of the problem is always resulted from the unique maximum solution and a minimal solution of the feasible region. A method is proposed to generate random feasible max-Dombi fuzzy relational inequalities and an algorithm is presented to solve the problem. Finally, an example is described to illustrate these algorithms.
Fuzzy relation,fuzzy relational inequality,linear optimization,fuzzy compositions and t-norms
https://jac.ut.ac.ir/article_69778.html
https://jac.ut.ac.ir/article_69778_67019cccd3ae9e759e6e2c4861660c90.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Tenacity and some other Parameters of Interval Graphs can be computed in polynomial time
81
87
EN
Dara
Moazzami
University of Tehran, College of Engineering, Faculty of Engineering Science
dmoazzami@ut.ac.ir
Niloofar
Vahdat
University of Tehran, Department of Algorithms and Computation
vahdat_n@alumni.ut.ac.ir
10.22059/jac.2018.69783
In general, computation of graph vulnerability parameters is NP-complete. In past, some algorithms were introduced to prove that computation of toughness, scattering number, integrity and weighted integrity parameters of interval graphs are polynomial.
In this paper, two different vulnerability parameters of graphs, tenacity and rupture degree are defined.
In general, computing the tenacity of a graph is NP-hard and the rupture degree of a graph is NP-complete, but in this paper, we will show that these parameters can be computed in polynomial time for interval graphs.
Vulnerability parameters,Tenacity,rupture degree,Interval graphs
https://jac.ut.ac.ir/article_69783.html
https://jac.ut.ac.ir/article_69783_125974741bf455d35e0263d2b3b55ef5.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Inverse eigenvalue problem for matrices whose graph is a banana tree
89
101
EN
Maryam
Babaei Zarch
Department of Computer Science, Yazd University, Yazd, Iran.
maryam.babaei@stu.yazd.ac.ir
Seyed Abolfazl
Shahzadeh Fazeli
0000-0002-3724-8689
Department of Computer Science, Yazd University, Yazd, Iran.
fazeli@yazd.ac.ir
Seyed Mehdi
Karbassi
Department of Mathematical Science, Yazd University, Yazd, Iran.
smkarbassi@yazd.ac.ir
10.22059/jac.2018.69994
In this paper, we consider an inverse eigenvalue problem (IEP) for constructing a special kind of acyclic matrices. The problem involves the reconstruction of matrices whose graph is a banana tree. This is performed by using the minimal and maximal eigenvalues of all leading principal submatrices of the required matrix. The necessary and sufficient conditions<br />for the solvability of the problem is derived. An algorithm to construct the solution is provided.
Inverse eigenvalue problem,banana tree,leading principal minors,eigenvalue,graph of a matrix
https://jac.ut.ac.ir/article_69994.html
https://jac.ut.ac.ir/article_69994_2c6384790926c12c2f8526d4ea76dc44.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Minimizing the Number of Tardy Jobs on Single Machine Scheduling with Flexible Maintenance Time
103
119
EN
Fatemeh
Ganji
Department of Industrial Engineering,
Gopayegan University of Technology. Golpayegan, Iran
ganji@gut.ac.ir
Amir
Jamali
Department of Industrial Engineering,
Gopayegan University of Technology. Golpayegan, Iran
ajamali@gut.ac.ir
10.22059/jac.2018.70449
In this study, single machine scheduling with flexible maintenance is investigated with non-resumable jobs by minimizing the weighted number of tardy jobs. It is assumed that the machine stops for a constant interval time during the scheduling period to perform maintenance. In other words, the starting time of maintenance is the decision variable. By reviewing the literature, we noticed that this problem has not been studied yet. Initially, it is proved that the problem is NP-hard. Then, a mathematical model is proposed and solved by the GAMS software. Because of the long time for solving the problem with an exact method, we develop a heuristic algorithm. To evaluate the efficiency of the proposed algorithm, 696 test problems with different sizes of the problem in the range from 1 to 2000 jobs, are generated. The computational results demonstrate that the average error of solution is 10.93\%.
Scheduling,Single machine,Flexible maintenance,Tardy job
https://jac.ut.ac.ir/article_70449.html
https://jac.ut.ac.ir/article_70449_f9a5d9d44b0de2068a18eff346e228c3.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Sign Test for Fuzzy Random Variables
121
139
EN
Mehdi
Shams
Department of Mathematical Sciences, University of Kashan, Isfahan, Iran.
mehdishams@kashanu.ac.ir
Gholamreza
Hesamian
Department of Statistics, Payame Noor University, Tehran, 19395-3697, Iran.
gh.hesamian@pnu.ac.ir
10.22059/jac.2018.70450
This paper extends the sign test to the case where data are observations of fuzzy random variables, and the hypotheses are imprecise rather than crisp. In this approach, first a new notion of fuzzy random variables is introduced. Then, the $\alpha$-level sets of the imprecise observations are transacted to extend the usual method of sign test. To do this, the concepts of fuzzy median and fuzzy sample median are defined.<br />We also develop a well-known large sample property of the classical sample median. In addition, the test statistic is extended for investigating fuzzy hypothesis. After that, applying an index called credibility degree, the degree that the observed fuzzy test statistics belongs to the critical region is evaluated. The result provides a fuzzy test function which leads to some degrees to accept or to reject the fuzzy null hypothesis.<br />A numerical example is provided to clarify the discussions made in this paper.
Sign test,fuzzy median,fuzzy sample median,fuzzy test statistic,credibility index,optimistic value,degree of belonging
https://jac.ut.ac.ir/article_70450.html
https://jac.ut.ac.ir/article_70450_0a2fe9c34dd4bab68198b0dde50a274c.pdf
University of Tehran
Journal of Algorithms and Computation
2476-2776
2476-2784
50
issue 2
2018
12
30
Changes in Artificial Neural Network Learning Parameters and Their Impact on Modeling Error Reduction
141
155
EN
Somayeh
Mehrabadi
Free scholar
somayeh.mehrabadi@yahoo.com
10.22059/jac.2018.70904
The main objective of this research is to investigate the effect of neural network architecture parameters on model behavior. Neural network architectural factors such as training algorithm, number of hidden layer neurons, data set design in training stage and the changes made to them, and finally its effect on the output of the model were investigated. It developed a database for modeling using by multi-layer perceptron. In particular, the modeling process enjoyed three training algorithms: Bayesian Regularization (BR), Scaled Conjugate Gradient (SCG) and Levenberg Marquardt (LM). Model selection criteria based on the lowest error rate and data regression, using a trial and error approach. The results showed that models that greatly reduce the error have less generalizability. In the meantime, the BR algorithm with the data set design of 15-15-70 (for test, validation and training sections, respectively), has been used to reduce the error better than other algorithms, but improper generalizability. In contrast, the LM algorithm has better generalizability than the other two algorithms. Data analysis shows that, in most cases, when the amounts of data dedicated to test and validation change (increase or decrease), the model requires more neurons in order to reduce errors.
https://jac.ut.ac.ir/article_70904.html
https://jac.ut.ac.ir/article_70904_d98c02626eb1d645dbddd9b9ccc2beb0.pdf