Knowledge and Information Systems (02191377)66(12)pp. 7717-7738
Automatic text summarization is the process of shortening a large document into a summary text that preserves the main concepts and key points of the original document. Due to the wide applications of text summarization, many studies have been conducted on it, but evaluating the quality of generated summaries poses significant challenges. Selecting the appropriate evaluation metrics to capture various aspects of summarization quality, including content, structure, coherence, readability, novelty, and semantic relevance, plays a crucial role in text summarization application. To address this challenge, the main focus of this study is on gathering and investigating a comprehensive set of evaluation metrics. Analysis of various metrics can enhance the understanding of the evaluation method and leads to select appropriate evaluation text summarization systems in the future. After a short review of various automatic text summarization methods, we thoroughly analyze 42 prominent metrics, categorizing them into six distinct categories to provide insights into their strengths, limitations, and applicability. © The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature 2024.
Rajaati bavil olyaei, M.,
Alambardar, M.,
Hooshmandasl, M.R.,
Shakiba, A. Journal of Combinatorial Optimization (13826905)48(4)
A mixed dominating set in a graph G=(V,E) is a subset D of vertices and edges of G such that every vertex and edge in (V∪E)\D is a neighbor of some elements in D. The mixed domination number of G, denoted by γmd(G), is the minimum size among all mixed dominating sets of G. For natural numbers n and k, where n>2k, a generalized Petersen graph P(n, k) is a graph with vertices {v0,v1,…,vn-1}∪{u0,u1,…,un-1} and edges ∪0≤i≤n-1{vivi+1,viui,uiui+k} where subscripts are modulo n. In this paper, we explicitly construct an optimal mixed dominating set for generalized Petersen graphs P(n, k) for k∈{1,2}. Moreover, we establish some upper bound on mixed domination number for other generalized Petersen graphs. © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024.
Discrete Mathematics and Theoretical Computer Science (14627264)26(3)
A subset S of vertices in a graph G = (V, E) is a Dominating Set if each vertex in V (G) \S is adjacent to at least one vertex in S. Chellali et al. in 2013, by restricting the number of neighbors in S of a vertex outside S, introduced the concept of [1, j]-dominating set. A set D ⊆ V of a graph G = (V, E) is called a [1, j]-Dominating Set of G if every vertex not in D has at least one neighbor and at most j neighbors in D. The Minimum [1, j]-Domination problem is the problem of finding the minimum [1, j]-dominating set D. Given a positive integer k and a graph G = (V, E), the [1, j]-Domination Decision problem is to decide whether G has a [1, j]-dominating set of cardinality at most k. A polynomial-time algorithm was obtained in split graphs for a constant j in contrast to the Dominating Set problem which is NP-hard for split graphs. This result motivates us to investigate the effect of restriction j on the complexity of [1, j]-domination problem on various classes of graphs. Although for j ≥ 3, it has been proved that the minimum of domination is equal to minimum [1, j]-domination in interval graphs, the complexity of finding the minimum [1, 2]-domination in interval graphs is still outstanding. In this paper, we propose a polynomial-time algorithm for computing a minimum [1, 2]-dominating set on interval graphs by a dynamic programming technique. Next, on the negative side, we show that the minimum [1, 2]-dominating set problem on circle graphs is NP-complete. © 2024 by the author(s)
With the increasing use of mobile phones and messaging services, SMS spam has become a significant issue for users. In this paper, we propose a novel approach1 to tackle this problem by using Sine-Cosine Algorithm (SCA) and Complex Multi-Layer Perceptron (C-MLP). Specifically, we apply the SCA method to reduce the dimensionality of the feature space and CMLP to improve the performance of spam detection. Also, in this paper, we investigate the effectiveness of different classification algorithms, including Support Vector Machines, Random Forests, K-nearest neighbors, Naive Bayes, bagging, and voting approaches. Our experimental results show that the proposed approach achieves high accuracy and outperforms existing methods in terms of both accuracy and F-measure. The proposed approach can be helpful in designing effective SMS spam filters and improving the overall user experience.1All the code used in this research is publicly available on the first author's GitHub repository: https://github.com/seper-sw/SMS-Spam-Detection.git © 2023 IEEE.
Discrete Mathematics, Algorithms and Applications (17938317)14(8)
A set D a V of a graph G = (V,E) is called an efficient dominating set of G if every vertex v has exactly one neighbor in D, in other words, the vertex set V is partitioned to some circles with radius one such that the vertices in D are the centers of partitions. A generalization of this concept, introduced by Chellali et al. [k-Efficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109-122], is called k-efficient dominating set that briefly partitions the vertices of graph with different radiuses. It leads to a partition set {U1,U2,..,Ut} such that each Ui consists a center vertex ui and all the vertices in distance di, where di {0, 1,..,k}. In other words, there exist the dominators with various dominating powers. The problem of finding minimum set {u1,u2,..,ut} is called the minimum k-efficient domination problem. Given a positive integer S and a graph G = (V,E), the k-efficient Domination Decision problem is to decide whether G has a k-efficient dominating set of cardinality at most S. The k-efficient Domination Decision problem is known to be NP-complete even for bipartite graphs [M. Chellali, T. W. Haynes and S. Hedetniemi, k-Efficient partitions of graphs, Commun. Comb. Optim. 4 (2019) 109-122]. Clearly, every graph has a k-efficient dominating set but it is not correct for efficient dominating set. In this paper, we study the following: k-efficient domination problem set is NP-complete even in chordal graphs. A polynomial-Time algorithm for k-efficient domination in trees. k-efficient domination on sparse graphs from the parametrized complexity perspective. In particular, we show that it is W[1]-hard on d-degenerate graphs while the original dominating set has Fixed Parameter Tractable (FPT) algorithm on d-degenerate graphs. k-efficient domination on nowhere-dense graphs is FPT. © 2022 World Scientific Publishing Company.
Alambardar, M.,
Goharshady, A.,
Hooshmandasl, M.R.,
Shakiba, A.,
Alambardar, M.,
Goharshady, A.,
Hooshmandasl, M.R.,
Shakiba, A. 2025 29th International Computer Conference, Computer Society of Iran, CSICC 2025pp. 266-273
Following the Bitcoin model, many modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain's protocol and is not under the miner's control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. The problem is known to be NP-hard. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting a well-known graph sparsity parameter, namely pathwidth, we present an exact linear-time parameterized algorithm that is applicable to the real-world instances and obtains optimal results. We also provide an experimental evaluation demonstrating that our approach outperforms current Bitcoin miners in practice, obtaining a significant increase in transaction fee revenues. © 2022 IEEE.
Electronic Journal Of Graph Theory And Applications (23382287)9(2)pp. 277-300
Given a positive integer k and a graph G = (V, E), a function f from V to the power set of Ik is called a k-rainbow function if for each vertex v ∈ V, f(v) = 0 implies ∪u∈N(v)f(u) = Ik where N(v) is the set of all neighbors of vertex v and Ik = {1,…, k}. Finding a k-rainbow function of minimum weight of Σv∈V |f(v)|, which is called the k-rainbow domination problem, is known to be NP-complete for arbitrary graphs and values of k. In this paper, we propose a dynamic programming algorithm to solve the k-rainbow domination problem for graphs with bounded tree-width tw in O ((2k+1 + 1)tw w n) time, where G has n vertices. Moreover, we also show that the same approach is applicable to solve the weighted k-rainbow domination problem with the same complexity Therefore, both problems of k-rainbow and weighted k-rainbow domination belong to the class FPT, or fixed parameter tractable, with respect to tree-width. In addition to formally showing the correctness of our algorithms, we also implemented these algorithms to illustrate some examples. © 2021
Iranian Journal Of Mathematical Sciences And Informatics (20089473)15(2)pp. 117-128
We study relations between evidence theory and S-approximation spaces. Both theories have their roots in the analysis of Dempster’s mul-tivalued mappings and lower and upper probabilities, and have close relations to rough sets. We show that an S-approximation space, satisfying a monotonicity condition, can induce a natural belief structure which is a fundamental block in evidence theory. We also demonstrate that one can induce a natural belief structure on one set, given a belief structure on another set, if the two sets are related by a partial monotone S-approximation space. © 2020 Academic Center for Education, Culture and Research TMU.
Sharifani, P.,
Hooshmandasl, M. R.,
Sharifani p., ,
Hooshmandasl, M.R.,
Alambardar, M. AKCE INTERNATIONAL JOURNAL OF GRAPHS AND COMBINATORICS (09728600)(3)pp. 870-876
A dominating set in a graph G is a subset of vertices D such that every vertex in V\D is a neighbor of some vertex of D. The domination number of G is the minimum size of a dominating set of G and it is denoted by gamma (G). A dominating set with cardinality gamma (G) is called optimal dominating set. Also, a subset D of a graph G is a [1, 2]-set if, each vertex v is an element of V\D is adjacent to either one or two vertices in D and the minimum cardinality of [1, 2]-dominating set of G, is denoted by gamma [1,2](G). Chang's conjecture says that for every 16 <= m <= n,gamma (Gm,n)=(n+2)(m+2)5-4 and this conjecture has been proven by Goncalves et al. This paper presents an explicit constructing method to find an optimal dominating set for grid graph G(m)(,)(n) where m,n >= 16 in O (size of answer). In addition, we will show that gamma (Gm,n)=gamma [1,2](Gm,n) where m,n >= 16 holds in response to an open question posed by Chellali et al.
Fuzzy Information And Engineering (16168658)12(4)pp. 529-544
Firefly algorithm is one of the latest outstanding bio-inspired algorithms, which could be manipulated in solving continuous or discrete optimisation problems. In this context, we have utilised the firefly algorithm accompanied by five well-known models of feature selection classifiers to have an accurate estimation of risk, and further to improve the interpret-ability of credit card prediction. One of the significant challenges in the real-world datasets is how to select features. As most of the datasets are unbalanced, the selection of features turns to the maximum class of data that is not fair. To overcome this issue, we have balanced the data using the SMOTE method. Our experimental results on four datasets show that balancing data has increased accuracy. In addition, using a hybrid firefly algorithm, the optimal combination of features that predicts the target class label is achieved. The selected features by the proposed method besides been reduced can represent both majority and minority classes. © 2021 The Author(s). Published by Informa UK Limited, trading as Taylor & Francis Group.
Theoretical Computer Science (03043975)804pp. 207-218
For a graph G, a set D⊆V(G) is called a [1,j]-dominating set if every vertex in V(G)∖D has at least one and at most j neighbors in D. A set D⊆V(G) is called a [1,j]-total dominating set if every vertex in V(G) has at least one and at most j neighbors in D. In the [1,j]-(TOTAL) DOMINATING SET problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [1,j]-(total) dominating set of size at most k. The [1,j]-DOMINATING SET problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [1,2]-TOTAL DOMINATING SET problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the DOMINATING SET problem, both are W[1]-hard when parameterized by solution size. In this work, we study the aforementioned problems on various graph classes from the perspective of parameterized complexity and prove the following results: • [1,j]-DOMINATING SET parameterized by solution size is W[1]-hard on d-degenerate graphs for d=j+1. • [1,j]-DOMINATING SET parameterized by solution size is FPT on nowhere dense graphs. • The known algorithm for [1,j]-DOMINATING SET on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). • Assuming SETH, we provide a lower bound for the running time of any algorithm solving the [1,2]-TOTAL DOMINATING SET problem parameterized by pathwidth. • Finally, we study another variant of DOMINATING SET, called RESTRAINED DOMINATING SET, that asks if there is a dominating set D of G of size at most k such that no vertex outside of D has all of its neighbors in D. We prove this variant is W[1]-hard even on 3-degenerate graphs. © 2019 Elsevier B.V.
Discrete Mathematics, Algorithms and Applications (17938317)11(2)
A set D ⊆ V for the graph G = (V,E) is called a dominating set if any vertex v ∈ V\D has at least one neighbor in D. Fomin et al. [Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications, ACM Transactions on Algorithms (TALG) 5(1) (2008) 9] gave an algorithm for enumerating all minimal dominating sets with n vertices in O(1.7159 n ) time. It is known that the number of minimal dominating sets for interval graphs and trees on n vertices is at most 3 n/3 ≈ 1.4422 n . In this paper, we introduce the domination cover number as a new criterion for evaluating the dominating sets in graphs. The domination cover number of a dominating set D, denoted by C D (G), is the summation of the degrees of the vertices in D. Maximizing or minimizing this parameter among all minimal dominating sets has interesting applications in many real-world problems, such as the art gallery problem. Moreover, we investigate this concept for different graph classes and propose some algorithms for finding the domination cover number in trees and block graphs. © 2019 World Scientific Publishing Company.
Discrete Applied Mathematics (0166218X)198pp. 136-146
A set S⊆V of the graph G=(V,E) is called a [1,2]-set of G if any vertex which is not in S has at least one but no more than two neighbors in S. A set S'⊆V is called a [1,2]-total set of G if any vertex of G, no matter in S' or not, is adjacent to at least one but not more than two vertices in S'. In this paper we introduce a linear algorithm for finding the cardinality of the smallest [1,2]-sets and [1,2]-total sets of a tree and extend it to a more generalized version for [i,j]-sets, a generalization of [1,2]-sets. This answers one of the open problems proposed in Chellali et al. (2013). Then since not all trees have [1,2]-total sets, we devise a recursive method for generating all the trees that do have such sets. This method also constructs every [1,2]-total set of each tree that it generates. © 2015 Elsevier B.V. All rights reserved.
International Journal of Bifurcation and Chaos (17936551)26(7)
In this work, we propose a class of public-key cryptosystems called multiplicative coupled cryptosystem, or MCC for short, as well as discuss its security within three different models. Moreover, we discuss a chaotic instance of MCC based on the first and the second types of Chebyshev polynomials over real numbers for these three security models. To avoid round-off errors in floating point arithmetic as well as to enhance the security of the chaotic instance discussed, the Chebyshev polynomials of the first and the second types over a finite field are employed. We also consider the efficiency of the proposed MCCs. The discussions throughout the paper are supported by practical examples. © 2016 World Scientific Publishing Company.
