Best-first search can be regarded as anytime scheme for producing lower bounds on the optimal solution, a characteristic that is mostly overlooked. We explore this topic in the context of AND/OR best-first search, guided by the MBE heuristic, when solving graphical models. In that context, the impact of the secondary heuristic for subproblem ordering may be significant, especially in the anytime context. Indeed, our paper illustrates this, showing that a new concept of bucket errors can advise in providing effective subproblem orderings in AND/OR search for both exact and anytime solutions.
Diaz, J.; Pottonen, O.; Serna, M.; van Leeuwen, E.J. Journal of computer and system sciences Vol. 83, num. 1, p. 132-158 DOI: 10.1016/j.jcss.2016.06.006 Data de publicació: 2017-04-03 Article en revista
The metric dimension of a graph G is the size of a smallest subset L ¿ V (G) such that for any x, y ¿ V (G) with x =/ y there is a z ¿ L such that the graph distance between x and z differs from the graph distance between y and z. Even though this notion has been part of the literature for almost 40 years, prior to our work the computational complexity of determining the metric dimension of a graph was still very unclear. In this paper, we show tight complexity boundaries for the Metric Dimension problem. We achieve this by giving two complementary results. First, we show that the Metric Dimension problem on planar graphs of maximum degree 6 is NP-complete. Then, we give a polynomial-time algorithm for determining the metric dimension of outerplanar graphs.
Data deduplication is an attractive technology to reduce storage space for increasing vast amount of duplicated and redundant data. In a cloud storage system with data deduplication, duplicate copies of data will be eliminated and only one copy will be kept in the storage. To protect the confidentiality of sensitive data while supporting deduplication, the convergent encryption technique has been proposed to encrypt the data before outsourcing. However, the issue of keyword search over encrypted data in deduplication storage system has to be addressed for efficient data utilization. This paper firstly proposes two constructions which support secure keyword search in this scenario. In these constructions, the integrity of the data can be realized by just checking the convergent key, without other traditional integrity auditing mechanisms. Then, two extensions are presented to support fuzzy keyword search and block-level deduplication. Finally, security analysis is given.
Barolli, A.; Oda, T.; Ikeda, M.; Barolli, L.; Xhafa, F.; Loia, V. Journal of computer and system sciences Vol. 81, num. 8, p. 1496-1507 DOI: 10.1016/j.jcss.2014.12.024 Data de publicació: 2015-12-01 Article en revista
Wireless Mesh Networks (WMNs) are attracting a lot of attention from wireless network researchers. Node placement problems have been investigated for a long time in the optimization field due to numerous applications in location science. In our previous work, we evaluated WMN-GA system which is based on Genetic Algorithms (GAs) to find an optimal location assignment for mesh routers. In this paper, we evaluate the performance of four different distributions of mesh clients (Normal, Uniform, Exponential and Weibull) considering Packet Delivery Ratio (PDR), throughput and delay metrics. For simulations, we used ns-3 and Hybrid Wireless Mesh Protocol (HWMP) and sent multiple Constant Bit Rate (CBR) flows in the network. The simulation results show that the implemented system can be used successfully for router placement in WMNs.
Community networks are a successful example of a collective where communities operate ICT infrastructure based on the principle of reciprocal sharing of network bandwidth. Cloud computing, common in today's Internet, has however not materialised within community networks. We analyse in this paper socio-technical characteristics of community networks in order to derive scenarios for community clouds. Based on an architecture for such a community cloud, we implement a prototype for the incentive-driven resource assignment component and evaluate its behaviour experimentally. In simulations of large-scale community cloud scenarios we study the behaviour of the incentive mechanism in different configurations. Our evaluation gives insight into how the developed mechanisms regulate the consumption of cloud resources. Our results suggest a further integration of this regulation component into current cloud management platforms in order to open them up for the operation of an ecosystem of collaborative cloud services in community networks. (C) 2014 Elsevier Inc. All rights reserved.
Xhafa, F.; Sánchez, C.; Barolli, A.; Takizawa, M. Journal of computer and system sciences Vol. 81, num. 8, p. 1417-1428 DOI: 10.1016/j.jcss.2014.12.018 Data de publicació: 2015-12-01 Article en revista
Wireless Mesh Networks (WMNs) are an important networking paradigm that offer cost effective Internet connectivity. The performance and operability of WMNs depend, among other factors, on the placement of network nodes in the area. Among the most important objectives in designing a WMN is the formation of a mesh backbone to achieve high user coverage. Given a number of router nodes to deploy, a deployment area and positions of client nodes in the area, an optimization problem can be formulated aiming to find the placement of router nodes so as to maximize network connectivity and user coverage. This optimization problem belongs to facility location problems, which are computationally hard to solve to optimality. In this paper we present the implementation and evaluation of Tabu Search (TS) for the problem of mesh router node placement in WMNs. The experimental evaluation showed the efficiency of TS in solving a benchmark of instances.
Tree-width and path-width are two well-studied parameters of structures that measure their similarity to a tree and a path, respectively. We show that QBF on instances with constant path-width, and hence constant tree-width, remains PSPACE-complete. This answers a question by Vardi. We also show that on instances with constant path-width and a very slow-growing number of quantifier alternations (roughly inverse-Ackermann many in the number of variables), the problem remains NP-hard. Additionally, we introduce a family of formulas with bounded tree-width that do have short refutations in Q-resolution, the natural generalization of resolution for quantified Boolean formulas.
The displacement calculus of Morrill, Valentín and Fadda (2011)  aspires to replace the calculus of Lambek (1958)  as the foundation of categorial grammar by accommodating intercalation as well as concatenation while remaining free of structural rules and enjoying Cut-elimination and its good corollaries. Jäger (2005)  proposes a type logical treatment of anaphora with syntactic duplication using limited contraction. Morrill and Valentín (2010)  apply (modal) displacement calculus to anaphora with lexical duplication and propose extension with a negation as failure in conjunction with additives to capture binding conditions. In this paper we present an account of anaphora developing characteristics and employing machinery from both of these proposals.
Xhafa, F.; Herrero , X.; Barolli, A.; Barolli, L.; Takizawa, M. Journal of computer and system sciences Vol. 79, num. 7, p. 1086-1100 DOI: 10.1016/j.jcss.2013.01.023 Data de publicació: 2012-02-12 Article en revista
Ground station scheduling problem arises in spacecraft operations and aims to allocate ground stations to spacecraft to make possible the communication between operations teams and spacecraft systems. The problem belongs to the family of satellite scheduling for the specific case of mapping communications to ground stations. The allocation of a ground station to a mission (e.g. telemetry, tracking information, etc.) has a high cost, and automation of the process provides many benefits not only in terms of management, but in economic terms as well. The problem is known for its high complexity as it is an over-constrained problem. In this paper, we present the resolution of the problem through Struggle Genetic Algorithms - a version of GAs that distinguishes for its efficiency in maintaining the diversity of the population during genetic evolution.
Ground station scheduling problem arises in spacecraft operations and aims to allocate ground stations to spacecraft to make possible the communication between operations teams and spacecraft systems. The problem belongs to the family of satellite scheduling for the specific case of mapping communications to ground stations. The allocation of a ground station to a mission (e.g. telemetry, tracking information, etc.) has a high cost, and automation of the process provides many benefits not only in terms of management, but in economic terms as well. The problem is known for its high complexity as it is an over-constrained problem. In this paper, we present the resolution of the problem through Struggle Genetic Algorithms – a version of GAs that distinguishes for its efficiency in maintaining the diversity of the population during genetic evolution. We present some computational results obtained with Struggle GA using the STK simulation toolkit, which showed the efficiency of the method in solving the problem.