Fundamenta Informaticae - Volume 191, issue 2

Authors: Anoop, S.K.M. | Sarma, Jayalal

Article Type: Research Article

Abstract: Computing the rotation distance between two binary trees with n internal nodes efficiently (in poly (n ) time) is a long standing open question in the study of height balancing in tree data structures. In this paper, we initiate the study of this problem bounding the rank of the trees given at the input (defined in [1] in the context of decision trees). We define the rank-bounded rotation distance between two given full binary trees T 1 and T 2 (with n internal nodes) of rank at most r = max{rank(T 1 ), …rank(T 2 )}, denoted by dR (T 1 , T 2 ), as the length of the shortest sequence of rotations that transforms T 1 to T 2 with the restriction that the intermediate trees must be of rank at most r . We show that the rotation distance problem reduces in polynomial time to the rank bounded rotation distance problem. This motivates the study of the problem in the combinatorial and algorithmic frontiers. Observing that trees with rank 1 coincide exactly with skew trees (full binary trees where every internal node has at least one leaf as a child), we show the following results in this frontier:• We present an O (n 2 ) time algorithm for computing dR (T 1 , T 2 ). That is, when the given full binary trees are skew trees (we call this variant the skew rotation distance problem ) - where the intermediate trees are restricted to be skew as well. In particular, our techniques imply that for any two skew trees dR (T 1 , T 2 ) ≤ n 2 . • We show the following upper bound: for any two full binary trees T 1 and T 2 of rank r 1 and r 2 respectively, we have that: dR (T 1 , T 2 ) ≤ n 2 (1 + (2n + 1)(r 1 + r 2 – 2)) where r = max{r 1 , r 2 }. This bound is asymptotically tight for r = 1. We present an O (n 2 ) time algorithm for computing dR (T 1 , T 2 ). That is, when the given full binary trees are skew trees (we call this variant the skew rotation distance problem ) - where the intermediate trees are restricted to be skew as well. In particular, our techniques imply that for any two skew trees dR (T 1 , T 2 ) ≤ n 2 . We show the following upper bound: for any two full binary trees T 1 and T 2 of rank r 1 and r 2 respectively, we have that: dR (T 1 , T 2 ) ≤ n 2 (1 + (2n + 1)(r 1 + r 2 – 2)) where r = max{r 1 , r 2 }. This bound is asymptotically tight for r = 1. En route to our proof of the above theorems, we associate full binary trees to permutations and relate the rotation operation on trees to transpositions in the corresponding permutations. We give exact combinatorial characterizations of permutations that correspond to full binary trees and full skew binary trees under this association. We also precisely characterize the transpositions that correspond to the set of rotations in full binary trees. We also study bi-variate polynomials associated with binary trees (introduced by [2]), and show characterizations and algorithms for computing rotation distances for the case of full skew trees using them. Show more

DOI: 10.3233/FI-242173

Citation: Fundamenta Informaticae, vol. 191, no. 2, pp. 79-104, 2024

Authors: Golpek, Hande Tuncel | Aytac, Aysun

Article Type: Research Article

Abstract: Analysis of a network in terms of vulnerability is one of the most significant problems. Graph theory serves as a valuable tool for solving complex network problems, and there exist numerous graph-theoretic parameters to analyze the system’s stability. Among these parameters, the closeness parameter stands out as one of the most commonly used vulnerability metrics. Its definition has evolved to enhance the ease of formulation and applicability to disconnected structures. Furthermore, based on the closeness parameter, vertex residual closeness, which is a newer and more sensitive parameter compared to other existing parameters, has been introduced as a new graph vulnerability …index by Dangalchev. In this study, the outcomes of the closeness and vertex residual closeness parameters in Harary Graphs have been examined. Harary Graphs are well-known constructs that are distinguished by having n vertices that are k -connected with the least possible number of edges. Show more

Keywords: Graph vulnerability, closeness, vertex residual closeness

DOI: 10.3233/FI-242174

Citation: Fundamenta Informaticae, vol. 191, no. 2, pp. 105-127, 2024

Authors: Lindermayr, Alexander | Siebertz, Sebastian | Vigny, Alexandre

Article Type: Research Article

Abstract: We study the graph parameter elimination distance to bounded degree , which was introduced by Bulian and Dawar in their study of the parameterized complexity of the graph isomorphism problem. We prove that the problem is fixed-parameter tractable on planar graphs, that is, there exists an algorithm that given a planar graph G and integers d , k decides in time f (k , d ) · nc for a computable function f and constant c whether the elimination distance of G to the class of degree d graphs is at most …k . Show more

DOI: 10.3233/FI-242175

Citation: Fundamenta Informaticae, vol. 191, no. 2, pp. 129-140, 2024

Authors: Yang, Chenxu | Klasing, Ralf | He, Changxiang | Mao, Yaping

Article Type: Research Article

Abstract: Foucaud et al . recently introduced and initiated the study of a new graph-theoretic concept in the area of network monitoring. Given a graph G = (V (G ), E (G )), a set M ⊆ V (G ) is a distance-edge-monitoring set if for every edge e ∈ E (G ), there is a vertex x ∈ M and a vertex y ∈ V (G ) such that the edge e belongs to all shortest paths between x and y . The smallest size of such a set in G …is denoted by dem(G ). Denoted by G – e (resp. G \u ) the subgraph of G obtained by removing the edge e from G (resp. a vertex u together with all its incident edges from G ). In this paper, we first show that dem(G – e ) – dem(G ) ≤ 2 for any graph G and edge e ∈ E(G ). Moreover, the bound is sharp. Next, we construct two graphs G and H to show that dem(G ) – dem(G \u ) and dem(H \ v ) – dem(H ) can be arbitrarily large, where u ∈ V (G ) and v ∈ V (H ). We also study the relation between dem(H ) and dem(G ), where H is a subgraph of G . In the end, we give an algorithm to judge whether the distance-edge-monitoring set still remain in the resulting graph when any edge of a graph G is deleted. Show more

Keywords: Distance, Perturbation result, Distance-edge-monitoring set, 05C12, 11J83, 35A30, 51K05

DOI: 10.3233/FI-242176

Citation: Fundamenta Informaticae, vol. 191, no. 2, pp. 141-163, 2024