Fundamenta Informaticae - Volume 174, issue 1

Authors: Ahmad, Ali | Asim, Muhammad Ahsan | Assiri, Basem | Semaničová-Feňovčíková, Andrea

Article Type: Research Article

Abstract: A vertex labeling φ : V (G ) → {1, 2, . . . , k } is called an edge irregular k-labeling of a graph G if all edges in G have unique weights. The weight of an edge is defined as the sum of the labels of its incident vertices. The minimum k for which the graph G has an edge irregular k -labeling is called the edge irregularity strength of G , denoted by es (G ). In this paper we perform a computer based experiment dealing with the edge …irregularity strength of complete bipartite graphs. We also present some bounds on this parameter for wheel related graphs. Show more

Keywords: edge irregularity strength, bipartite graph, wheel graph, fan graph, friendship graph, naive algorithm

DOI: 10.3233/FI-2020-1927

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 1-13, 2020

Authors: Çiftçi, Canan | Aytaç, Vecdi

Article Type: Research Article

Abstract: A set S ⊆ V (G ) is a disjunctive total dominating set of G if every vertex has a neighbor in S or has at least two vertices in S at distance 2 from it. The disjunctive total domination number is the minimum cardinality of a disjunctive total dominating set in G . We define the disjunctive total domination subdivision number of G as the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) to increase the disjunctive total domination number. In this …paper, we first study the disjunctive total domination subdivision number of some special graphs. Next, we give some upper bounds on the disjunctive total domination subdivision number for any graphs in terms of vertex degree. Finally, we supply some conditions for a graph G to have a minimum disjunctive total domination subdivision number. Show more

Keywords: domination, disjunctive total domination, subdivision

DOI: 10.3233/FI-2020-1928

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 15-26, 2020

Authors: Konishi, Tatsuya | Kojima, Hideharu | Nakagawa, Hiroyuki | Tsuchiya, Tatsuhiro

Article Type: Research Article

Abstract: Combinatorial interaction testing is an efficient software testing strategy. If all interactions among test parameters or factors needed to be covered, the size of a required test suite would be prohibitively large. In contrast, this strategy only requires covering t -wise interactions where t is typically very small. As a result, it becomes possible to significantly reduce test suite size. Locating arrays aim to enhance the ability of combinatorial interaction testing. In particular, ( 1 ¯ , t ) -locating arrays can not only execute all t -way interactions but also identify, …if any, which of the interactions causes a failure. In spite of this useful property, there is only limited research either on how to generate locating arrays or on their minimum sizes. In this paper, we propose an approach to generating minimum locating arrays. In the approach, the problem of finding a locating array consisting of N tests is represented as a Constraint Satisfaction Problem (CSP) instance, which is in turn solved by a modern CSP solver. The results of using the proposed approach reveal many ( 1 ¯ , t ) -locating arrays that are smallest known so far. In addition, some of these arrays are proved to be minimum. Show more

Keywords: Software testing, combinatorial interaction testing, locating array, constraint satisfaction problem

DOI: 10.3233/FI-2020-1929

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 27-42, 2020

Authors: Turacı, Tufan

Article Type: Research Article

Abstract: The concept of vulnerability is very important in network analysis. Several existing parameters have been proposed in the literature to measure network vulnerability, such as domination number, average lower domination number, residual domination number, average lower residual domination number, residual closeness and link residual closeness. In this paper, incorporating the concept of the domination number and link residual closeness number, as well as the idea of the average lower domination number, we introduce new graph vulnerability parameters called the link residual domination number, denoted by γ LR (G ), and the average lower link residual domination number, denoted by …γ a v L R ( G ) , for any given graph G . Furthermore, the exact values and the upper and lower bounds for any graph G are given, and the exact results of well-known graph families are computed. Show more

Keywords: Network Design and Communication, Graph vulnerability, Domination number, Link residual closeness, Residual domination number, Average lower residual domination number

DOI: 10.3233/FI-2020-1930

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 43-59, 2020

Authors: Andrejczuk, Ewa | Alberola, Juan M. | Marcolino, Leandro | Torroni, Paolo

Article Type: Other

DOI: 10.3233/FI-2020-1931

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 61-62, 2020

Authors: Andrés, Ignasi | de Barros, Leliane Nunes | Delgado, Karina Valdivia

Article Type: Research Article

Abstract: Contingent planning models a robot that must achieve a goal in a partially observable environment with non-deterministic actions. A solution for this problem is generated by searching in the space of belief states , where a belief state is a set of possible world states. However, if there is an unavoidable dead-end state, the robot will fail to accomplish his task. In this work, rather than limiting a contingent planning task to the agent’s actions and observations, we model a planning agent that is able to proactively resort to humans for help in order to complete tasks that would …be unsolvable otherwise. Our aim is to develop a symbiotic autonomous agent, that is, an agent that, proactively and autonomously, asks for human help when needed. We formalize this problem and propose an extension of a translation technique to convert the contingent planning problem with human help into a non-deterministic fully observable planning problem that can be solved by an off-the-shelf efficient FOND planner. Show more

DOI: 10.3233/FI-2020-1932

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 63-81, 2020

Authors: Manyà, Felip | Negrete, Santiago | Roig, Carme | Soler, Joan Ramon

Article Type: Research Article

Abstract: Given a classroom containing a fixed number of students and a fixed number of tables that can be of different sizes, as well as a list of preferred classmates to sit with for each student, the team composition problem in a classroom (TCPC) is the problem of finding an assignment of students to tables in such a way that the preferences of students are maximally-satisfied. In this paper, we first formally define the TCPC, prove that it is NP-hard and define two different MaxSAT models of the problem, called maximizing and minimizing encoding. Then, we report on the results of …an empirical investigation that show that solving the TCPC with MaxSAT solvers is a promising approach and provide evidence that the minimizing encoding outperforms the maximizing encoding. Finally, we illustrate how the proposed MaxSAT-based modeling approach is also well-suited for modeling other more complex team formation problems. Show more

Keywords: Team creation, MaxSAT, NP-hard, encoding, optimization solver

DOI: 10.3233/FI-2020-1933

Citation: Fundamenta Informaticae, vol. 174, no. 1, pp. 83-101, 2020