Fundamenta Informaticae - Volume 182, issue 3

Authors: Chehreghani, Mostafa Haghir | Bifet, Albert | Abdessalem, Talel

Article Type: Research Article

Abstract: Graphs (networks) are an important tool to model data in different domains. Realworld graphs are usually directed , where the edges have a direction and they are not symmetric. Betweenness centrality is an important index widely used to analyze networks. In this paper, first given a directed network G and a vertex r ∈ V (G ), we propose an exact algorithm to compute betweenness score of r . Our algorithm pre-computes a set ℛ𝒱(r ), which is used to prune a huge amount of computations that do not contribute to the betweenness score of r …. Time complexity of our algorithm depends on |ℛ𝒱(r )| and it is respectively Θ(|ℛ𝒱(r )| · |E (G )|) and Θ(|ℛ𝒱(r )| · |E (G )| + |ℛ𝒱(r )| · |V (G )| log |V (G )|) for unweighted graphs and weighted graphs with positive weights. |ℛ𝒱(r )| is bounded from above by |V (G )| – 1 and in most cases, it is a small constant. Then, for the cases where ℛ𝒱(r ) is large, we present a simple randomized algorithm that samples from ℛ𝒱(r ) and performs computations for only the sampled elements. We show that this algorithm provides an (ɛ , δ )-approximation to the betweenness score of r . Finally, we perform extensive experiments over several real-world datasets from different domains for several randomly chosen vertices as well as for the vertices with the highest betweenness scores. Our experiments reveal that for estimating betweenness score of a single vertex, our algorithm significantly outperforms the most efficient existing randomized algorithms, in terms of both running time and accuracy. Our experiments also reveal that our algorithm improves the existing algorithms when someone is interested in computing betweenness values of the vertices in a set whose cardinality is very small. Show more

Keywords: Social networks, directed graphs, betweenness centrality, exact algorithm, approximate algorithm

DOI: 10.3233/FI-2021-2071

Citation: Fundamenta Informaticae, vol. 182, no. 3, pp. 219-242, 2021

Authors: Jin, Yu | Song, Bosheng | Li, Yanyan | Zhu, Ying

Article Type: Research Article

Abstract: Membrane computing is a branch of natural computing aiming to abstract computing models from the structure and functioning of living cells. The computation models obtained in the field of membrane computing are usually called P systems. P systems have been used to solve computationally hard problems efficiently on the assumption that the execution of each rule is completed in exactly one time-unit (a global clock is assumed for timing and synchronizing the execution of rules). However, in biological reality, different biological processes take different times to be completed, which can also be influenced by many environmental factors. In this work, …with this biological reality, we give a time-free solution to independent set problem using P systems with active membranes, which solve the problem independent of the execution time of the involved rules. Show more

Keywords: bio-inspired computing, membrane computing, cell-like P system, time-free solution, independent set problem

DOI: 10.3233/FI-2021-2072

Citation: Fundamenta Informaticae, vol. 182, no. 3, pp. 243-255, 2021

Authors: Nguyen, Viet Dung | Pham, Ba Thai | Do, Phan Thuan

Article Type: Research Article

Abstract: We first design an 𝒪 (n 2 ) solution for finding a maximum induced matching in permutation graphs given their permutation models, based on a dynamic programming algorithm with the aid of the sweep line technique. With the support of the disjoint-set data structure, we improve the complexity to 𝒪 (m +n ). Consequently, we extend this result to give an 𝒪 (m +n ) algorithm for the same problem in trapezoid graphs. By combining our algorithms with the current best graph identification algorithms, we can solve the MIM problem in permutation and trapezoid graphs in linear and 𝒪 (n …2 ) time, respectively. Our results are far better than the best known 𝒪 (mn ) algorithm for the maximum induced matching problem in both graph classes, which was proposed by Habib et al. Show more

Keywords: permutation graph, trapezoid graph, induced matching, sweep line, disjoint set

DOI: 10.3233/FI-2021-2073

Citation: Fundamenta Informaticae, vol. 182, no. 3, pp. 257-283, 2021

Authors: Jessy Sujana, G. | Rajalaxmi, T.M. | Rajasingh, Indra | Sundara Rajan, R.

Article Type: Research Article

Abstract: A zero forcing set is a set S of vertices of a graph G , called forced vertices of G , which are able to force the entire graph by applying the following process iteratively: At any particular instance of time, if any forced vertex has a unique unforced neighbor, it forces that neighbor. In this paper, we introduce a variant of zero forcing set that induces independent edges and name it as edge-forcing set. The minimum cardinality of an edge-forcing set is called the edge-forcing number. We prove that the edge-forcing problem of determining the edge-forcing number is …NP-complete. Further, we study the edge-forcing number of butterfly networks. We obtain a lower bound on the edge-forcing number of butterfly networks and prove that this bound is tight for butterfly networks of dimensions 2, 3, 4 and 5 and obtain an upper bound for the higher dimensions. Show more

Keywords: Zero forcing set, forced vertex, independent set, edge-forcing set, butterfly networks

DOI: 10.3233/FI-2021-2074

Citation: Fundamenta Informaticae, vol. 182, no. 3, pp. 285-299, 2021

Authors: Zarrabi, Mohammad Reza | Charkari, Nasrollah Moghaddam

Article Type: Research Article

Abstract: We study the query version of constrained minimum link paths between two points inside a simple polygon P with n vertices such that there is at least one point on the path, visible from a query point. The method is based on partitioning P into a number of faces of equal link distance from a point, called a link-based shortest path map (SPM). Initially, we solve this problem for two given points s , t and a query point q . Then, the proposed solution is extended to a general case for three arbitrary query points …s , t and q . In the former, we propose an algorithm with O (n ) preprocessing time. Extending this approach for the latter case, we develop an algorithm with O (n 3 ) preprocessing time. The link distance of a q-visible path between s , t as well as the path are provided in time O (log n ) and O (m + log n ), respectively, for the above two cases, where m is the number of links. Show more

Keywords: Computational Geometry, Minimum Link Path, Shortest Path Map, Map Overlay

DOI: 10.3233/FI-2021-2075

Citation: Fundamenta Informaticae, vol. 182, no. 3, pp. 301-319, 2021