Fundamenta Informaticae - Volume 163, issue 4

Authors: Henry, Christopher J. | Awais, Syed Aqeel

Article Type: Research Article

Abstract: This article proposes the tolerance nearness measure (TNM) as a computationally reduced alternative to the graph edit distance (GED) for performing graph comparisons. The TNM is defined within the context of near set theory, where the central idea is that determining similarity between sets of disjoint objects is at once intuitive and practically applicable. The TNM between two graphs is produced using the Bron-Kerbosh maximal clique enumeration algorithm. The result is that the TNM approach is less computationally complex than the bipartite-based GED algorithm. The contribution of this paper is the application of TNM to the problem of quantifying the …similarity of disjoint graphs and that the maximal clique enumeration-based TNM produces comparable results to the GED when applied to the problem of content-based image processing, which becomes important as the number of nodes in a graph increases. Show more

Keywords: Graph matching, Tolerance nearness measure, Graph edit distance, Near sets, Maximal clique enumeration

DOI: 10.3233/FI-2018-1746

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 305-324, 2018

Authors: Kheirfam, Behrouz | Nasrollahi, Afsaneh

Article Type: Research Article

Abstract: We present a primal-dual path-following interior-point method for linear optimization that is based on the integer powers of the square root function. Our derived search directions is a generalization of the standard directions and the search directions given by Darvay. The proposed algorithm uses only full steps and hence no need to perform line search. We first prove that the iterates lie in the quadratic convergence neighborhood of the proximity measure and then derive the iteration-complexity bound for the algorithm.

Keywords: Linear optimization, full-Newton step, feasible interior-point method, small-update methods, polynomial complexity

DOI: 10.3233/FI-2018-1747

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 325-337, 2018

Authors: Manuel, Paul | Klavžar, Sandi

Article Type: Research Article

Abstract: Given a graph G , the (graph theory) general position problem is to find the maximum number of vertices such that no three vertices lie on a common geodesic. This graph invariant is called the general position number (gp-number for short) of G and denoted by gp(G ). In this paper, the gp-number is determined for a large class of subgraphs of the infinite grid graph and for the infinite diagonal grid. To derive these results, we introduce monotone-geodesic labeling and prove a Monotone Geodesic Lemma that is in turn developed using the Erdös-Szekeres theorem on monotone sequences. The …gp-number of the 3-dim infinite grid is bounded. Using isometric path covers, the gp-number is also determined for Beneš networks. Show more

Keywords: general position problem, monotone-geodesic labeling, interconnection networks, isometric subgraph, infinite grids, Beneš networks

DOI: 10.3233/FI-2018-1748

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 339-350, 2018

Authors: Mishra, Sumit | Mondal, Samrat | Saha, Sriparna

Article Type: Research Article

Abstract: Cluster validity indices are proposed in the literature to measure the goodness of a clustering result. The validity measure provides a value which shows how good or bad the obtained clustering result is, as compared to the actual clustering result. However, the validity measures are not arbitrarily generated. A validity measure should satisfy some of the important properties. However, there are cases when in-spite of satisfying these properties, a validity measure is not able to differentiate the two clustering results correctly. In this regard, sensitivity as a property of validity measure is introduced to capture the differences between the two …clustering results. However, sensitivity computation is a computationally expensive task as it requires to explore all the possible combinations of clustering results which are very large in number and these are growing exponentially. So, it is required to compute the sensitivity efficiently. As the possible combinations of clustering results grow exponentially, so it is required to first obtain an upper bound on this possible number of combinations which will be sufficient to compute the value of the sensitivity. In this paper, we obtain an upper bound on the number of possible combinations of clustering results. For this purpose, a generic approach which is suitable for various validity measures and a specific approach which is applicable for two validity measures are proposed. It is also shown that this upper bound is sufficient to compute the sensitivity of various validity measures. This upper bound is very less as compared to the total number of possible combinations of clustering results. Show more

Keywords: Clustering algorithm, sensitivity, cluster validity measure

DOI: 10.3233/FI-2018-1749

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 351-374, 2018

Authors: Shaw, Dipan Lal | Islam, A.S.M. Shohidull | Karmaker, Shuvasish | Rahman, M. Sohel

Article Type: Research Article

Abstract: Predicting the secondary structure of a protein using a lattice model is one of the most studied computational problems in bioinformatics. Here the secondary structure or three dimensional structure of a protein is predicted from its amino acid sequence. The secondary structure refers to the local sub-structures of a protein. Simplified energy models have been proposed in the literature on the basis of interaction of amino acid residues in proteins. We focus on a well researched model known as the Hydrophobic-Polar (HP) energy model. In this paper, we propose the hexagonal prism lattice with diagonals that can overcome the problems …of other lattice structures, e.g., parity problem. We give two approximation algorithms for protein folding on this lattice using HP model. Our first algorithm leads us to a similar structure of helix structure that is commonly found in a protein structure. This motivates us to propose the next algorithm with a better approximation ratio. Finally, we analyze the algorithms on the basis of intensity of the chemical forces along the different types of edges of hexagonal prism lattice with diagonals. Show more

DOI: 10.3233/FI-2018-1750

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 375-393, 2018

Authors: Tian, Miaomiao | Wang, Lingyan | Zhong, Hong | Chen, Jie

Article Type: Research Article

Abstract: Cloud storage is a significant service provided by the cloud that enables users to store their immense data into the cloud. As the advent of the big data era, cloud storage services are becoming increasingly popular. For security reasons, data owners would like to check the integrity of their data after storing it in the cloud. To do this, they usually make use of the public cloud data integrity checking schemes. This paper focuses on user anonymity in such schemes so that no third party could infer the identity information of any data owner from checking procedures. The problem is …obviously inevitable in reality, however the current solutions are relatively involved as they heavily use public key certificates and/or incur huge communication overhead. In this paper we introduce the concept of attribute-based cloud data integrity checking to achieve user anonymity lightly and present security models for such systems. We also provide a practical construction and prove its security in the random oracle model. Finally, we show how to extend our construction to protect data privacy against any third party. Show more

Keywords: Cloud storage, Data integrity, User anonymity, Attribute-based cryptography

DOI: 10.3233/FI-2018-1751

Citation: Fundamenta Informaticae, vol. 163, no. 4, pp. 395-411, 2018