Search

We consider the problem of computing the diameter of a unicycle graph (i.e., a graph with a unique cycle). We present an O (n) time algorithm for the problem, where n is the number of vertices of the graph. This improves the previous best O (n log ⁡ n) time solution [Oh and Ahn, ISAAC 2016]. Using this algorithm as a subroutine, we solve the problem of adding a shortcut to a tree so that the diameter of the new graph (which is a unicycle graph) is minimized; our algorithm takes O (n 2 log ⁡ n) time and O (n) space. The previous best algorithms solve the problem in O (n 2 log 3 ⁡ n) time and O (n) space [Oh and Ahn, ISAAC 2016], or in O (n 2) time and O (n 2) space [Bilò, ISAAC 2018]. • The paper presents a linear time algorithm for computing the diameter of unicycle graphs. • The paper gives a new algorithm which finds a new edge to add to a tree so that the diameter of the new graph is minimized. • The algorithms rely on certain domination relations among edges of the graphs. [ABSTRACT FROM AUTHOR]

In the 2-Club Cluster Vertex Deletion (resp., 2-Club Cluster Edge Deletion) problem the input is a graph G and an integer k , and the goal is to decide whether there is a set of at most k vertices (resp., edges) whose removal from G results in a graph in which the diameter of every connected component is at most 2. In this paper we give algorithms for 2-Club Cluster Vertex Deletion and 2-Club Cluster Edge Deletion whose running times are O ⁎ (3.104 k) and O ⁎ (2.562 k) , respectively. Our algorithms were obtained using automated generation of branching rules. Our results improve the previous O ⁎ (3.303 k) -time algorithm for 2-Club Cluster Vertex Deletion [Liu et al., FAW-AAIM 2012] and the O ⁎ (2.695 k) -time algorithm for 2-Club Cluster Edge Deletion [Abu-Khzam et al., TCS 2023]. [ABSTRACT FROM AUTHOR]

Over the past decades, the Gathering problem , which asks to gather a group of robots in finite time given some restrictions, has been intensively studied. In this paper, we are given a group of n autonomous, dimensionless, deterministic, and anonymous robots, with bounded viewing range. Assuming a continuous time model, the goal is to gather these robots into one point in finite time. We introduce a simple convergence criterion that defines a new class of algorithms which perform gathering in O (n d) time, where d is the diameter of the initial robot configuration. We show that some gathering algorithms in the literature belong to this class and propose two new algorithms that belong to this class and have quadratic running time, namely, Go-To-The-Relative-Center algorithm (GTRC) and Safe-Go-To-The-Relative-Center algorithm (S-GTRC). We prove that the latter can perform gathering without collision by using a slightly more complex robot model: non oblivious, chiral, and luminous (i.e. robots have observable external memory, as in [8]). We also consider a variant of the Gathering problem, the Near-Gathering problem, in which robots must get close to each other without colliding. We show that S-GTRC solves the Near-Gathering problem in quadratic time and assumes a weaker robot model than the one assumed in the current state-of-the-art. [ABSTRACT FROM AUTHOR]

Given an edge-weighted undirected graph G = (V , E , w) and a subset T ⊆ V of p terminals, a k-Steiner forest spanning all the terminals in T includes k branches, where every branch is a Steiner tree. The diameter of a k -Steiner forest is referred to as the maximum distance between two terminals of a branch. This paper studies the minimum diameter k-Steiner forest problem (MD k SFP) and establishes the relationship between MD k SFP and the absolute k-Steiner center problem (A k SCP). We first obtain a 2-factor dual approximation algorithm for A k SCP, and then achieve a 2-approximation algorithm for MD k SFP based on the 2-approximation to A k SCP. Furthermore, we develop an improved 2 ρ -approximation algorithm for MD k SFP, where ρ < 1 in general, by perturbing the sites of facilities and re-clustering the terminals. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is distance hereditary if every induced path of G is a shortest path. In this paper, we show that the eccentricity function e (v) = max ⁡ { d (v , u) : u ∈ V } in any distance-hereditary graph G is almost unimodal, that is, every vertex v with e (v) > r a d (G) + 1 has a neighbor with smaller eccentricity. Here, r a d (G) = min ⁡ { e (v) : v ∈ V } is the radius of graph G. Moreover, we use this result to fully characterize the centers of distance-hereditary graphs. Several bounds on the eccentricity of a vertex with respect to its distance to the center of G or to the ends of a diametral path are established. Finally, we propose a new linear time algorithm to compute all eccentricities in a distance-hereditary graph. [ABSTRACT FROM AUTHOR]

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

In this paper, we consider rainbow connection number of maximal outerplanar graphs (MOPs) on algorithmic aspect. For the (MOP) G , we give sufficient conditions to guarantee that r c ( G ) = d i a m ( G ) . Moreover, we produce the graph with given diameter D and give their rainbow coloring in linear time. X. Deng et al. [4] give a polynomial time algorithm to compute the rainbow connection number of MOPs by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri [11] proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut-spine of MOP G , by which we design an algorithm to give a rainbow edge coloring with at most 2 r a d ( G ) + 2 + c , 0 ≤ c ≤ r a d ( G ) − 2 colors in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer , it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15–29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61–72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977–979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147–157] and it has been open for a long time whether this problem can be solved in time. In this paper, we will provide a simple and efficient -time algorithm for solving this problem. [Copyright &y& Elsevier]

A double-loop digraph G=G(N;s1,s2), with gcd(N,s1,s2)=1, has the set of vertices V=ZN and the adjacencies are given by u→u+si (mod N) i=1,2. The diameter of G, denoted by D(N;s1,s2), is known to be lower bounded by lb(N) withThis lower bound is known to be sharp. For a fixed N∈N, some algorithms to find D(N) and steps 1⩽α<β such that D(N;α,β)=D(N) are known through the bibliography, being of numerical nature all of them.In this paper we propose a symbolic algorithm on the following problem: Given a number of vertices N0∈N, find if possible an infinite family of tight double-loop digraphs G(x)=G(N(x);s1(x),s2(x)) such that N(x0)=N0 and D(x)=D(N(x);s1(x),s2(x))=lb(N(x)) ∀x⩾x0. This family is parameterized by the integer x with N(x)∈Z and s1(x),s2(x)∈Z/(N(x)). As a direct consequence of such an explicit family of digraphs G(x), we also have an additive basis {s1(x),s2(x)} which covers the elements of Z/(N(x)) with optimal order.The time cost of this algorithm is O(√ of N0 log N0), in the worst case. [Copyright &y& Elsevier]