Search

Fruit recognition and location are the premises of robot automatic picking. YOLOv3 has been used to detect different fruits in complex environment. However, for the object with definite features, the complex network structure will increase the computing time and may cause overfitting. Therefore, this paper has carried out a lightweight design for the YOLOv3. This paper proposed an improved T-Net to detect tomato images. Firstly, the T-Net reduces the residual network layers. This paper changed the number of cycles in each group of the residual unit to 1, 2, 2, 1, and 1. Second, two feature layers with different scales are selected according to the features of tomatoes. Meanwhile, the convolutional layer at the neck has been reduced by two layers. Finally, the location and approximate diameter of the ripe tomato are obtained by combining the node information of the Intel D435i camera and T-Net in the Robot Operation System. T-Net obtains mean average precision (mAP) of 99.2%, F1-score of 98.9%, precision of 99.0%, and recall of 98.8% at a detection rate of 104.2 FPS. The proposed T-Net has outperformed the YOLOv3 with 0.4%, 0.1%, and 0.2% increase in precision, mAP, and F1-score. The detection speed of T-Net is 1.8 times faster than YOLOv3. The mean errors of the center coordinates and diameter of the tomato are 8.5 mm and 2.5 mm, respectively. This model provides a method for efficient real-time detection and location of tomatoes. [ABSTRACT FROM AUTHOR]

This paper studies the optimization of hydraulic parameters for pipeline system of hydropower station with super long headrace tunnel (HSSLHT) based on mayfly algorithm considering operational scenarios. Firstly, the state equation of HSSLHT under load disturbance is derived. The optimization design of hydraulic parameters for pipeline system based on mayfly algorithm is proposed. Then, the optimization of hydraulic parameters is conducted and analyzed. Finally, the effects of pipeline diameters and transfer coefficients of turbines on the optimization of hydraulic parameters for pipeline systems are revealed. The results show that the optimization of hydraulic parameters for pipeline system is a multiobjective problem, and the several objective functions exhibit significant conflicts. Compared to the firefly algorithm and genetic algorithm, the objective function under mayfly algorithm is improved by 14.7% and 5.1%, respectively. The mayfly algorithm can make the hydraulic parameters for the pipeline system reach the Pareto optimal solution under both load decrease condition and load increase condition. The diameter of penstock has an obvious influence on the robustness of dynamic performance of HSSLHT. When the diameter of penstock increases by 30%, the robustness of HSSLHT becomes worse and the robustness index deteriorates by 57%. The reason is that the flow inertia of penstock becomes smaller with the increase of diameter, and the flow inertia of penstock is favorable for resisting disturbance of HSSLHT. The coefficient of throttled orifice head loss and the lengths and head losses of headrace tunnel and penstock are the key hydraulic parameters for matching the operation of HSSLHT. [ABSTRACT FROM AUTHOR]

In order to improve the accuracy of extracting tree breast diameter from backpack laser scanning（BLS） data, this paper filtered out the noise points whose BLS scan data was more than 10 cm away from the nearest point, and used the irregular triangulation algorithm to extract the ground point, and subtracted the elevation value of the point cloud from the corresponding ground point elevation value to normalize the elevation of the point cloud data. At an elevation of 0.8 to 1.8 m, slice with a step of 0.1 m, and filter out different point clouds to extract DBH. The smallest diameter of the fitting circle of all slices in each tree was selected as the diameter at breast height of the tree, and the results of the test results, measured data and the results of extracting DBH from point cloud only after preprocessed were compared. The results showed that by filtering out low intensity point clouds, the root mean square error（RMSE） of the three plots were reduced from 2.63 cm to 0.99 cm, 5.43 cm to 4.72 cm, and 4.01 m to 2.15 cm, the average error decreased from 1.90 cm to 0.79 cm, 5.24 cm to 4.16 cm, and 3.36 cm to 1.58 cm. In the forest data scanned by BLS, the point cloud with low intensity at breast diameter was a point cloud with large stitching error, which would affect the accuracy of the breast diameter extraction result. Filtering out this part of the point cloud can improve the accuracy. The proportion of large stitching error point clouds was related to the terrain, and the proportion of low quality point clouds on slopes was larger than that on flat ground. [ABSTRACT FROM AUTHOR]

Aiming at the problem that the classic puncture path planning algorithm does not consider the area around the path when quantifying the path, new constraints condition are proposed to make up for the lack of quantification of the information around the path. A strict constraint condition was proposed based on the blood vessel position information (the surrounding area avoids the blood vessel), and based on bone density, blood vessel density, and diameter information, three soft constraints (bone density, blood vessel density, and blood vessel risk) were proposed, and the surrounding information was added to the quantification of the path to improve the safety of the puncture path. In order to adapt to the specificity of patients, a soft constraint optimization degree scoring algorithm is proposed, and the weight is set according to the optimization degree of soft constraints, and the puncture path corresponding to the maximum optimization degree is taken as the optimal puncture path. In order to verify the effectiveness of the algorithm, experiments were carried out on the public dataset 3D-IRCADb. The experimental results show that the algorithm proposed in this paper can quickly calculate the optimal puncture path that meets the clinical needs. [ABSTRACT FROM AUTHOR]

In order to explore the optimal control method of tennis racket string diameter, this paper applies the Kalman filter algorithm to the collection and processing of tennis sports parameters. When the Kalman filter uses the optimal gain (the Kalman filter enters the steady state), the corresponding cost function is established based on the noncorrelated nature of its residual sequence, which is used as the judgment condition for the sampling strategy switch to improve the stability of the system. In addition, this paper improves the real-time performance and calculation accuracy of data transformation through adaptive sampling strategy and adaptive scale factor, improves the stability and estimation accuracy of the system as a whole, and builds an intelligent monitoring system. Finally, this paper systematically studied the optimization control method of tennis racket string diameter and verified that the Kalman filter algorithm can play a certain role in the optimization control of tennis racket string diameter. [ABSTRACT FROM AUTHOR]

For a connected graph G (V , E) , we use the notation d (a 1 , a 2) to represent the distance between two node points a 1 and a 2 and it is the minimum of the lengths of all paths between them. The eccentricity e (a) of a node point a ∈ V is considered as the maximum length of all shortest paths starts from a to the remaining nodes, i.e., e (a) = max { d (a , u 1) : u 1 ∈ V }. The diameter of a graph G , we denote it by d (G) and it is the length of the longest shortest path in G , i.e., d (G) = max { e (a) : a ∈ V }. Also, the radius of a graph G , we denote it by the symbol r (G) and it is the least eccentricity of all node points in V , i.e., r (G) = min { e (a) : a ∈ V }. The central vertex/node point x of a graph G is a node whose eccentricity is same as G 's radius, i.e., e (x) = r (G). The collection of all central nodes of a graph G is considered as the center of G and it is symbolized by c (G) , i.e., c (G) = { x ∈ V : e (x) = r (G) }. A graph may have one or more central vertices. This paper develops an optimal algorithm to compute the diameter, radius and central node (s) of the permutation graph having n node points in O (n) time. We have also established a tight relation between radius and diameter of permutation graphs. [ABSTRACT FROM AUTHOR]

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]

The new trend to design a data center network is to deploy switches and two-port servers on the nodes and edges in an interconnection network, the logic graph of which can be abstracted as a compound graph. Node-independent spanning tree (NIST) is an important structure that can be used to design reliable communication protocols, fault-tolerant broadcasting, and secure message distribution, IP fast rerouting, etc in data center networks. Given a compound graph G (Kn), this paper firstly showed that if the diameter of G was d, then the diameter of G( Kn) was either 2d or 2d + 1. Supposed that there were n NIST rooted at an arbitrary node in an n-regular n-node-connected interconnection network G, this paper presented a unified method to construct n NIST in G (Kn) by proposing an efficient algorithm with time complexity 0 (N), where N was the number of nodes . Ana-lysis of NIST on compound graph Qn(Kn) shows that the maximal height is only the diameter plus 3 . Also, simulation experiments on the augmented based on data center networks show the correctness from another aspect. [ABSTRACT FROM AUTHOR]

In this paper, precipitation rate retrieval algorithms for the Global Precipitation Measurement mission's Dualfrequency Precipitation Radar (DPR) are developed. The DPR consists of a Ku-band radar (KuPR; 13.6 GHz) and a Ka-band radar (KaPR; 35.5 GHz). For the KuPR, an algorithm similar to the Tropical Rainfall Measuring Mission's Precipitation Radar algorithm is developed, with the relation between precipitation rate R and massweighted mean diameter Dm (R-Dm relation) replacing the relation between the specific attenuation k and effective radar reflectivity factor Ze. The R-Dm relation can also be applied to the KaPR and dual-frequency algorithms. In both the single-frequency and dual-frequency algorithms, the forward retrieval method is applied with an assumed adjustment factor for the R-Dm relation (ε) and the results are evaluated to select the best value of ε. The advantages of the dual-frequency algorithm are the availability of the dual-frequency surface reference technique and the ZfKa method, which is a method to use the attenuation-corrected radar reflectivity factor Zf of KaPR, to select ε as well as the possibility to selectively use measurements from KuPR or KaPR. This paper also describes the derivation of the scattering table and the R-Dm relation as well as the procedure for non-uniform beam filling correction in detail. The outputs are then statistically analyzed to demonstrate algorithm performance. [ABSTRACT FROM AUTHOR]

This paper focuses on studying the message complexity of implicit leader election in synchronous distributed networks of diameter two. Kutten et al. (J ACM 62(1):7:1–7:27, 2015) showed a fundamental lower bound of Ω (m) (m is the number of edges in the network) on the message complexity of (implicit) leader election that applied also to Monte Carlo randomized algorithms with constant success probability; this lower bound applies for graphs that have diameter at least three. On the other hand, for complete graphs (i.e., graphs with diameter one), Kutten et al. (Theor Comput Sci 561(Part B):134–143, 2015) established a tight bound of Θ ~ (n) on the message complexity of randomized leader election (n is the number of nodes in the network). For graphs of diameter two, the complexity was not known. In this paper, we settle this complexity by showing a tight bound of Θ ~ (n) on the message complexity of leader election in diameter-two networks. We first give a simple randomized Monte-Carlo leader election algorithm that with high probability (i.e., probability at least 1 - n - c , for some fixed positive constant c) succeeds and uses O (n log 3 n) messages and runs in O(1) rounds; this algorithm works without knowledge of n (and hence needs no global knowledge). We then show that any algorithm (even Monte Carlo randomized algorithms with large enough constant success probability) needs Ω (n) messages (even when n is known), regardless of the number of rounds. We also present an O (n log n) message deterministic algorithm that takes O (log n) rounds (but needs knowledge of n); we show that this message complexity is tight for deterministic algorithms. Together with the two previous results of Kutten et al., our results fully characterize the message complexity of leader election vis-à-vis the graph diameter. [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]

In this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d for several types of inputs. We get optimal algorithms when the time complexities are linear. Let the size of input (convex polyhedron P /set S of points/convex polyhedra) be n / N , respectively, size of distance function convex polygon/polyhedron Q be m and size of constraint convex polyhedral region R be r in plane or ℜ d. The radius, incenter and circumcenter of the convex polygon P in ℜ 2 can be optimally computed in linear time, i.e. O (n + m) and in time O (n + m + r) , if the incenter or circumcenter is additionally constrained in a convex polygon/polyhedron R. In ℜ d , the radius, incenter and circumcenter of a convex polyhedron as well as of a set of convex polyhedra, unconstrained or constrained, can be computed in O (N m) and O (N m + r) time respectively, for convex constraint polyhedral region R. We also compute the minimum stabbing sphere for a set of convex polyhedra, unconstrained or constrained, for the above mentioned distance functions in O (N m) -time or O (N m + r) -time respectively for convex constraint polyhedral region R in ℜ d. The diameter of a convex polygon in plane can be computed in O (n + m) time and the diameter of a convex polyhedron in ℜ d can be computed in O (n m) time. The width of a convex polyhedron can be computed in O (n + m) time and O (n 2 m) time, for ℜ 2 and ℜ d , respectively. The diameter and width of a set of convex polyhedra can be computed in O (N m) -time and (N 2 m) , respectively, in any dimensions. We also show how the k dimensional minimum enclosing/stabbing cylinder for the convex polyhedron P can be computed in O (n d − k + 2 m 2) in ℜ d and in O (n d m (n + m)) in ℜ d for k = 1. The k dimensional minimum enclosing/stabbing cylinder for the set of convex polyhedra S in ℜ d can be computed in O (N d − k + 2 m 2) -time. The diameter and width problems can also be solved for a set of points in ℜ d , either in time O (n m) or in time O (m T (n)) , where T (n) is the time complexity of the best convex hull computation algorithm for the given set of points. [ABSTRACT FROM AUTHOR]

We consider a well-studied generalization of the maximum clique problem which is defined as follows. Given a graph G on n vertices and a fixed parameter d ≥ 1 , in the maximum diameter-bounded subgraph problem (MaxDBS for short) the goal is to find a (vertex) maximum subgraph of G of diameter at most d. For d = 1 , this problem is equivalent to the maximum clique problem and thus it is NP-hard to approximate it within a factor n 1 - ϵ , for any ϵ > 0 . Moreover, it is known that, for any d ≥ 2 , it is NP-hard to approximate MaxDBS within a factor n 1 / 2 - ϵ , for any ϵ > 0 . In this paper we focus on MaxDBS for the class of unit disk graphs. We provide a polynomial-time constant-factor approximation algorithm for the problem. The approximation ratio of our algorithm does not depend on the diameter d. Even though the algorithm itself is simple, its analysis is rather involved. We combine tools from the theory of hypergraphs with bounded VC-dimension, k-quasi planar graphs, fractional Helly theorems, and several geometric properties of unit disk graphs. [ABSTRACT FROM AUTHOR]

In this paper we present a scaling algorithm for minimizing arbitrary functions over vertices of polytopes in an oracle model of computation which includes an augmentation oracle. For the binary case, when the vertices are 0–1 vectors, we show that the oracle time is polynomial. Also, this algorithm allows us to generalize some concepts of combinatorial optimization concerning performance bounds of greedy algorithms and leads to new bounds for the complexity of the simplex method. [ABSTRACT FROM AUTHOR]

Aiming at the influence of signal attenuation on nugget diameter evaluation results in ultrasonic testing of resistance spot welding, a gain compensation method based on wavelet transform for different frequency subband signals is proposed in this paper. Each subband signal is compensated and reconstructed respectively, and the nugget diameter is calculated by the reconstructed signal. This method is used to compensate the spot welding test signal and simulation signal respectively. The nugget diameter is calculated by the compensation signal, and the calculated value is compared with the measured value of nugget diameter. The results show that the method can effectively reduce the calculation error of nugget diameter by compensating the gain of ultrasonic testing signal. [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]

Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations, dierent clusterings of the same data set become relevant. For example, different algorithms for the same clustering task may return dramatically different solutions. We are interested in applications in which one clustering has to be transformed into another, e.g., when a gradual transition from an old solution to a new one is required. In this paper, we devise methods for constructing such a transition based on linear programming and network theory. We use a so-called clustering-difference graph to model the desired transformation and provide methods for decomposing the graph into a sequence of elementary moves that accomplishes the transformation. These moves are equivalent to the edge directions, or circuits, of the underlying partition polytopes. Therefore, in addition to a conceptually new metric for measuring the distance between clusterings, we provide new bounds on the circuit diameter of these partition polytopes. [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]

The fastest known algorithms for finding the exact value of the diameter of general graphs are no faster than the algorithms that compute all-pairs shortest paths. An extension of the problem of computing graph diameter is enumerating pairs of vertices in a graph, ordered decreasingly by their distance. In this paper, we investigate this problem with the presence of memory constraints. We also show how our result can help the computation of graph Hyperbolicity, by lowering the memory complexity of computing the ordered list of far-apart vertex pairs. [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]

The rings considered in this paper are commutative with identity which are not integral domains. Recall that an ideal of a ring is called an annihilating ideal if there exists such that . As in [M. Behboodi and Z. Rakeei, The annihilating-ideal graph of commutative rings I, J. Algebra Appl. 10(4) (2011) 727-739], for any ring , we denote by the set of all annihilating ideals of and by the set of all nonzero annihilating ideals of . Let be a ring. In [S. Visweswaran and H. D. Patel, A graph associated with the set of all nonzero annihilating ideals of a commutative ring, Discrete Math. Algorithm Appl. 6(4) (2014), Article ID: 1450047, 22pp], we introduced and studied the properties of a graph, denoted by , which is an undirected simple graph whose vertex set is and distinct elements are joined by an edge in this graph if and only if . The aim of this paper is to study the interplay between the ring theoretic properties of a ring and the graph theoretic properties of , where is the complement of . In this paper, we first determine when is connected and also determine its diameter when it is connected. We next discuss the girth of and study regarding the cliques of . Moreover, it is shown that is complemented if and only if is reduced. [ABSTRACT FROM AUTHOR]

Abstract Let P be a path graph of n vertices embedded in a metric space. We consider the problem of adding a new edge to P such that the diameter of the resulting graph is minimized. Previously (in ICALP 2015) the problem was solved in O (n log 3 ⁡ n) time. In this paper, based on new observations and different algorithmic techniques, we present an O (n log ⁡ n) time algorithm. [ABSTRACT FROM AUTHOR]

The Kautz digraphs K(d, ℓ) are a well-known family of dense digraphs, widely studied as a good model for interconnection networks. Closely related to these, the cyclic Kautz digraphs CK(d, ℓ) were recently introduced by Böhmová, Huemer and the author, and some of its distance-related parameters were fixed. In this paper we propose a new approach to the cyclic Kautz digraphs by introducing the family of the subKautz digraphs sK(d, ℓ), from where the cyclic Kautz digraphs can be obtained as line digraphs. This allows us to give exact formulas for the distance between any two vertices of both sK(d, ℓ) and CK(d, ℓ). Moreover, we compute the diameter and the semigirth of both families, also providing efficient routing algorithms to find the shortest path between any pair of vertices. Using these parameters, we also prove that sK(d, ℓ) and CK(d, ℓ) are maximally vertex-connected and super-edge-connected. Whereas K(d, ℓ) are optimal with respect to the diameter, we show that sK(d, ℓ) and CK(d, ℓ) are optimal with respect to the mean distance, whose exact values are given for both families when ℓ = 3. Finally, we provide a lower bound on the girth of CK(d, ℓ) and sK(d, ℓ). [ABSTRACT FROM AUTHOR]

Phylogenetic networks are a generalization of phylogenetic trees that allow for representation of reticulate evolution. Recently, a space of unrooted phylogenetic networks was introduced, where such a network is a connected graph in which every vertex has degree 1 or 3 and whose leaf-set is a fixed set X of taxa. This space, denoted N(X), is defined in terms of two operations on networks—the nearest neighbor interchange and triangle operations—which can be used to transform any network with leaf set X into any other network with that leaf set. In particular, it gives rise to a metric d on N(X) which is given by the smallest number of operations required to transform one network in N(X) into another in N(X). The metric generalizes the well-known NNI-metric on phylogenetic trees which has been intensively studied in the literature. In this paper, we derive a bound for the metric d as well as a related metric dNNI which arises when restricting d to the subset of N(X) consisting of all networks with 2(|X|-1+i) vertices, i≥1. We also introduce two new metrics on networks—the SPR and TBR metrics—which generalize the metrics on phylogenetic trees with the same name and give bounds for these new metrics. We expect our results to eventually have applications to the development and understanding of network search algorithms. [ABSTRACT FROM AUTHOR]

In this paper, we extend upon the results of B. Suceavă and R. Stong [Amer. Math. Monthly, 110 (2003) 162{162], which they computed the minimum number of 3-cycles needed to generate an even permutation. Let Ωnk,m be the set of all permutations of the form c1c2 · · · ck where ci's are arbitrary m-cycles in Sn. Suppose that Γnk,m be the Cayley graph on subgroup of Sn generated by all permutations in Ωnk,m. We find a shortest path joining identity and any vertex of Γnk,m for arbitrary natural number k, and m = 2, 3, 4. Also, we calculate the diameter of these Cayley graphs. As an application, we present an algorithm for finding a short expression of a permutation as products of given permutations. [ABSTRACT FROM AUTHOR]

This paper studies the geodesic diameter of polygonal domains having $$h$$ holes and $$n$$ corners. For simple polygons (i.e., $$h=0$$ ), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as shown by Hershberger and Suri. For general polygonal domains with $$h \ge 1$$ , however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time $$O(n^{7.73})$$ or $$O(n^7 (\log n + h))$$ . The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two. [ABSTRACT FROM AUTHOR]

We study recursive cubes of rings as models for interconnection networks. We first redefine each of them as a Cayley graph on the semidirect product of an elementary abelian group by a cyclic group in order to facilitate the study of them by using algebraic tools. We give an algorithm for computing shortest paths and the distance between any two vertices in recursive cubes of rings, and obtain the exact value of their diameters. We obtain sharp bounds on the Wiener index, vertex-forwarding index, edge-forwarding index and bisection width of recursive cubes of rings. The cube-connected cycles and cube-of-rings are special recursive cubes of rings, and hence all results obtained in the paper apply to these well-known networks. [ABSTRACT FROM AUTHOR]

A problem of practical and theoretical interest is to determine or estimate the diameter of various families of Cayley networks. The previously known estimate for the diameter of Cayley graphs generated by transposition trees is an upper bound given in the oft-cited paper of Akers and Krishnamurthy (1989). In this work, we first assess the performance of their upper bound. We show that for every n, there exists a tree on n vertices, such that the difference between the upper bound and the true diameter value is at least n - 4. Evaluating their upper bound takes time Ω(n!). In this paper, we provide an algorithm that obtains an estimate of the diameter, but which requires only time O(n²); furthermore, the value obtained by our algorithm is less than or equal to the previously known diameter upper bound. Such an improvement to polynomial time, while still performing at least as well as the previous bound, is possible because our algorithm works directly with the transposition tree on n vertices and does not require examining any of the permutations. We also provide a tree for which the value computed by our algorithm is not necessarily unique, which is an important result because such examples are quite rare. For all families of trees we have investigated so far, each of the possible values computed by our algorithm happens to also be an upper bound on the diameter. [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]

• A synergy planning methodology of energy stations and networks is proposed. • The cost-based synergy planning model consists of power losses, siting and sizing, multiple constraints. • The model uses a hybrid approach including Genetic Algorithm, Dijkstra Algorithm and Simulated Annealing. • Four scenarios analyze the potential benefits of the methodology. • The proposed hybrid approach is an efficient tool for siting and sizing energy stations and networks. Siting and sizing of energy stations (ESs) and pipeline networks (PNs) significantly influence views on the economy of regional integrated energy system (RIES). In this paper, we present a synergy planning method for siting and sizing ESs and PNs. This study describes the basic structure of ESs and PNs in RIES, clearly points out influencing factors that should be considered in the planning model. Then, with flow velocity, pipe diameter, equipment capacity, and the location of ESs and PNs as variables, the cost-based function model is built based on many constraints. The Genetic Algorithm (GA) based heuristic algorithm and the PNs planning algorithm based on "Dijkstra Algorithm (DA) + Simulated Annealing (SA)" are used to solve the problem proposed in this paper. In the results and discussion, the proposed model and method are verified by a hypothetical region from OpenStreetMap. The economic changes are studied in a basic scenario and three comparison scenarios. The results show that synergy planning can save 293,320 $ and reduce the load peak-valley difference rate by 3.24%. Moreover, optimizing the flow velocity can reduce 0–32.04% lowest annual cost (LAC). [ABSTRACT FROM AUTHOR]

In this paper, a novel streak-resolving algorithm is proposed for particle streak velocimetry (PSV) to resolve velocity fields for a single image frame with multiple particle streaks. A model streak function, which was based on the temporal integral of the particle image intensity moving along its trajectory during the exposure period, was approximated using a multivariable least-square fit procedure to reconstruct the streak information and the corresponding particle trajectory. Lagrangian tracking was achieved, and the velocities were evaluated by differentiating the resolved particle trajectory with respect to time. Two types of flows, accelerating parallel flow and the rotational flow of Hill's vortex, were used to generate synthetic streaks for the performance tests. Three types of relative error were defined and used to evaluate the performance of the algorithm in terms of statistical mean and standard deviation (SD) errors. The accuracy of the fitted streak parameters, such as particle image intensity and diameter, were also evaluated and compared. The results reveal that the error and SD were low if the image noise is below 1.0%; for noise levels of 5.0%, the error was up to 10% with an SD of up to 12%. The error and SD of the particle image intensity and particle image diameter for both flow types were also 0%–7% for clean and up to 12% for noisy images. The processing results for experimental streak images of flow past a cylinder reveal that these images can be resolved using the proposed algorithm with a residual mean error of 4.38 and an SD of 9.48. These results suggest that the proposed novel approach can be used to resolve velocity fields with only a single image frame and without expensive hardware for high-speed imaging and thus is suitable for diverse applications. • A post-processing algorithm for Particle Streak Velocimetry (PSV) to resolve particle streak images formed by long camera exposure time. • Extract spatial and temporal information to fully reconstruct particle trajectory as a function of time. • Obtain tangential velocity from the reconstructed trajectory at any point on a streak. • Validated by both synthetic and experimental streak images. • Errors of resolving the streak images quantified and the error sources discussed. [ABSTRACT FROM AUTHOR]

A star is a graph in which some node is incident with every edge of the graph, i.e., a graph of diameter at most 2. A star forest is a graph in which each connected component is a star. Given a connected graph G in which the edges may be weighted positively. A spanning star forest of G is a subgraph of G which is a star forest spanning the nodes of G. The size of a spanning star forest F of G is defined to be the number of edges of F if G is unweighted and the total weight of all edges of F if G is weighted. We are interested in the problem of finding a Maximum Weight spanning Star Forest (MWSFP) in G. In [C. T. Nguyen, J. Shen, M. Hou, L. Sheng, W. Miller and L. Zhang, Approximating the spanning star forest problem and its applications to genomic sequence alignment, SIAM J. Comput. 38(3) (2008) 946-962], the authors introduced the MWSFP and proved its NP-hardness. They also gave a polynomial time algorithm for the MWSF problem when G is a tree. In this paper, we present a linear time algorithm that solves the MSWF problem when G is a cactus. [ABSTRACT FROM AUTHOR]

The main focus of this paper is calculation of the diameters of asteroids belonging to five families (Vesta, Eos, Eunomia, Koronis, and Themis). To do that, we used the HCM algorithm applied for a data set containing 292,003 numbered asteroids, and a numerical procedure for choosing the crucial parameter of the HCM, called 'the cutting velocity' vcut. It was established with a precision as high as 1 m s−1. Thereafter, we used the WISE (Wide-field Infrared Survey Explorer) catalog to set a range of albedo for the largest members of each family considered. The albedo data were supported by the data concerning color classification ( SDSS MOC4). The asteroids with albedo out of this range were classified as interlopers and were therefore disqualified as family members. Sizes were calculated for the asteroids with albedo within the acceptable range. For the other asteroids (those chosen by means of the HCM, but with albedo not listed in the WISE), the value of albedo of the largest member of the family was adopted. Results are given in a set of figures showing the families on the planes ( a, e), ( a, i), ( e, i). Diameters and volumes of the asteroids that are the individual members of a family were calculated on the basis of their known or assumed albedo and on their absolute magnitude. Volumes of the parent bodies of the families were found on the basis of the cumulative volume distribution of these families. We also studied the secular resonances of the family members. We have shown that the locations of members of the considered asteroid families are related to the lines of secular resonances z1, z2, and z3 with Saturn. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, an automatic optical inspection system is designed specifically to measure the diameter and lens sag of large-size microlenses: 1. The proposed algorithm of measuring lens diameter locates the lens center through the Euclidean distance array, and determines the lens edge along an initiated ray using linear interpolation with sub-pixel accuracy. 2. The lens sag is calculated from a single fringe pattern of large-size microlens, in combination with the measured lens diameter. 3. According to the experiment results, the proposed system has advantages of high applicability, rapid processing speed, and good accuracy with the RMS error≤1% of measuring a large-size microlens, but without the requirement of prior training. The system architecture of non-contact measurement would not cause scratches on the lens surface and is inexpensive, thus, which is particularly suitable for the in-line inspection of industry field. [Copyright &y& Elsevier]

Accurate vehicle localization in forest environments is still an unresolved problem. Global navigation satellite systems (GNSS) have well known limitations in dense forest, and have to be combined with for instance laser based SLAM algorithms to provide satisfying accuracy. Such algorithms typically require accurate detection of trees, and estimation of tree center locations in laser data. Both these operations depend on accurate estimations of tree trunk diameter. Diameter estimations are important also for several other forestry automation and remote sensing applications. This paper evaluates several existing algorithms for diameter estimation using 2D laser scanner data. Enhanced algorithms, compensating for beam width and using multiple scans, were also developed and evaluated. The best existing algorithms overestimated tree trunk diameter by ca. 40%. Our enhanced algorithms, compensating for laser beam width, reduced this error to less than 12%. [ABSTRACT FROM AUTHOR]

The paper presents the complete design processes of novel aeration control systems in the SBR (sequencing batch reactor) wastewater treatment plant (WWTP). Due to large energy expense and a high influence on biological processes, the aeration system plays a key role in WWTP operation. The paper considers the aeration system for a biological WWTP located in the northeast of Poland. This system consists of blowers, the main collector pipeline, three aeration lines with different diameters and lengths, and diffusers. Classical control systems applied for this type of installation are based on PID (proportional–integral–derivative) controllers, the settings of which are often found experimentally. The article presents the optimization of these settings and the design of an alternative control algorithm—the fuzzy controller. [ABSTRACT FROM AUTHOR]

Given a convex n -gon, we can draw n disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the n disks and two disks are adjacent if and only if they have a point in common. Such a graph was introduced by Huemer and Pérez-Lantero (Discrete Mathematics, 2020), proved to be planar and Hamiltonian. In this paper, we study further combinatorial properties of this graph. We prove that the treewidth is at most 3, by showing an O (n) -time algorithm that builds a tree decomposition of width at most 3, given the polygon as input. This implies that we can construct the intersection graph of the side disks in O (n) time. We further study the independence number, which is the maximum number of pairwise disjoint disks. The planarity condition implies that for every convex n -gon we can select at least ⌈ n / 4 ⌉ pairwise disjoint disks, and we prove that for every n ≥ 3 there exist convex n -gons in which we cannot select more than this number. Finally, we show that our class of graphs includes all outerplanar Hamiltonian graphs except the cycle of length four, and that it is a proper subclass of the planar Hamiltonian graphs. [ABSTRACT FROM AUTHOR]

The eccentricity of a node in a graph is defined as the length of a longest shortest path starting at that node. The eccentricity distribution over all nodes is a relevant descriptive property of the graph, and its extreme values allow the derivation of measures such as the radius, diameter, center and periphery of the graph. This paper describes two new methods for computing the eccentricity distribution of large graphs such as social networks, web graphs, biological networks and routing networks.We first propose an exact algorithm based on eccentricity lower and upper bounds, which achieves significant speedups compared to the straightforward algorithm when computing both the extreme values of the distribution as well as the eccentricity distribution as a whole. The second algorithm that we describe is a hybrid strategy that combines the exact approach with an efficient sampling technique in order to obtain an even larger speedup on the computation of the entire eccentricity distribution. We perform an extensive set of experiments on a number of large graphs in order to measure and compare the performance of our algorithms, and demonstrate how we can efficiently compute the eccentricity distribution of various large real-world graphs. [ABSTRACT FROM AUTHOR]

This paper proposes an offline wavelength assignment technique for de Bruijn (d, k) optical wavelength division multiplexing (WDM) networks having nodal degree d and diameter k that can support lightpaths between pair of nodes. Each lightpath uses a channel (wavelength) along each link in its route. An efficient algorithm is proposed that can be used to assign wavelengths to lightpath requests in O(k|V|) time, where |V| represents the number of nodes of the de Bruijn network and V represents the set of nodes. The proposed algorithm can be efficiently used for wavelength assignment in de Bruijn WDM networks having limited wavelength conversion capabilities. This work shows that de Bruijn graph can be expressed as union of edge-disjoint rings. Wavelengths are assigned for the individual rings in the graph thus resulting in the assignment for the graph itself. Results are shown for a given de Bruijn graph and for an arbitrary request. The proposed algorithm is compared with two other algorithms, which use two other known works of wavelength assignment on ring topology. Comparisons of the time complexity and the type of wavelength conversion required for these algorithms clearly show that the proposed algorithm is a faster and more efficient way of assigning wavelengths. [ABSTRACT FROM PUBLISHER]

Abstract: The determination of arterial wave speed and the separation of the forward and backward waves have been established using simultaneous measurements of pressure (P) and velocity (U). In this work, we present a novel algorithm for the determination of local wave speed and the separation of waves using the simultaneous measurements of diameter (D) and U. The theoretical basis of this work is the solution of the 1D equations of flow in elastic tubes. A relationship between D and U is derived, from which, local wave speed can be determined; C=±0.5(dU ±/d ln D ±). When only unidirectional waves are present, this relationship describes a linear relationship between ln D and U. Therefore, constructing a ln DU-loop should result in a straight line in the early part of the cycle when it is most probable that waves are running in the forward direction. Using this knowledge of wave speed, it is also possible to derive a set of equations to separate the forward and backward waves from the measured D and U waveforms. Once the forward and backward waveforms of D and U are established, we can calculate the energy carried by the forward and backward waves, in a similar way to that of wave intensity analysis. In this paper, we test the new algorithm in vitro and present results from data measured in the carotid artery of human and the ascending aorta of canine. We conclude that the new technique can be reproduced in vitro, and in different vessels of different species, in vivo. The new algorithm is easy to use to determine wave speed and separate D and U waveforms into their forward and backward directions. Using this technique has the merits of utilising noninvasive measurements, which would be useful in the clinical setting. [Copyright &y& Elsevier]

In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining whether such an augmentation is possible for all graphs. In this paper, we answer this question negatively by exhibiting an infinite family of graphs that cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most O(log log n) are navigable. We show that for doubling dimension ⪢ log log n, an infinite family of graphs cannot be augmented to become navigable. Finally, we present a positive navigability result by studying the special case of square meshes of arbitrary dimension that we prove to always be augmentable to become navigable. This latter result complements Kleinberg's original result and shows that adding extra links can sometimes break the navigability. [ABSTRACT FROM AUTHOR]

Consider a connected graph and a configuration of pebbles on its vertices. A pebbling step consists of removing two pebbles from a vertex and placing one on an adjacent vertex. A configuration is called solvable if it is possible to place a pebble on any given vertex through a sequence of pebbling steps. A smallest number t such that any configuration with t pebbles is solvable is called the pebbling number of the graph. In this paper, we consider algorithms determining the solvability of a pebbling configuration on graphs of diameter two. We prove that if k is the vertex connectivity of a diameter two graph G, then a configuration is solvable if there are at least c(k) = min{k+4, 3k -1} vertices in G with two or more pebbles. We use this result to construct an algorithm that has complexity O(c(k)! · n2c(k)-3m), where n is the number of vertices and m is the number of edges. We also present an algorithm for diameter two graphs with pebbling number n+1, known as Class 1 graphs, which takes O(nm) time. [ABSTRACT FROM AUTHOR]

This paper describes a robust hybrid artificial neural network (ANN) methodology which can offer a superior performance for the important process engineering problems. The method incorporates a hybrid artificial neural network and differential evolution technique (ANN-DE) for the efficient tuning of ANN meta parameters. The algorithm has been applied for the prediction of the hold up of the solid liquid slurry flow. A comparison with selected correlations in the literature showed that the developed ANN correlation noticeably improved the prediction of hold up over a wide range of operating conditions, physical properties, and pipe diameters. [ABSTRACT FROM AUTHOR]

Metacyclic graphs, which include supertoroids as a subclass, have been shown to possess interesting properties and potential applications in implementing moderate- to large-size parallel processors with fairly small node degrees. Wu, Lakshmivarahan, and Dhall (J. Parallel Distrib. Comput. 60 (2000), pp. 539-565) have described a deterministic, distributed routing scheme for certain subclasses of metacyclic graphs. However, they offer no proof that the scheme is a shortest-path routing algorithm and do not indicate whether or how their scheme may be extended to the entire class of metacyclic graphs. In this paper, we provide a near-shortest-path, deterministic routing algorithm that is applicable to any metacyclic graph and derive a bound for the diameter of such graphs. [ABSTRACT FROM AUTHOR]

Let γ pr ( G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ pr ( G – v) < γ pr ( G). We call these graphs γ pr -critical. In this paper, we present a method of constructing γ pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ pr -critical graph is at most $$\frac{3}{2}(\gamma_{pr} (G)-2)$$ and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. [ABSTRACT FROM AUTHOR]

This paper presents and analyzes an incremental system for clustering streaming time series. The Online Divisive-Agglomerative Clustering (ODAC) system continuously maintains a tree-like hierarchy of clusters that evolves with data, using a top-down strategy. The splitting criterion is a correlation-based dissimilarity measure among time series, splitting each node by the farthest pair of streams. The system also uses a merge operator that reaggregates a previously split node in order to react to changes in the correlation structure between time series. The split and merge operators are triggered in response to changes in the diameters of existing clusters, assuming that in stationary environments, expanding the structure leads to a decrease in the diameters of the clusters. The system is designed to process thousands of data streams that flow at a high rate. The main features of the system include update time and memory consumption that do not depend on the number of examples in the stream. Moreover, the time and memory required to process an example decreases whenever the cluster structure expands. Experimental results on artificial and real data assess the processing qualities of the system, suggesting a competitive performance on clustering streaming time series, exploring also its ability to deal with concept drift. [ABSTRACT FROM AUTHOR]

Alternating group graphs AGn, studied by Jwo and others, Constitute a class of Cayley graphs that possess certain desirable properties compared with other regular networks considered by researchers in parallel and distributed computing. A different form, ANn, of such graphs, proposed by Youhou and dubbed alternating group networks, has been shown to possess advantages over AGn. For example, ANn has a node degree that is smaller by a factor of about 2 while maintaining a diameter comparable to that of AGn, is maximally fault-tolerant, and shares some of the positive structural attributes of the well-known star graph. In this paper, we characterize the distance between any two nodes in ANn and present an optimal (shortest-path) routing algorithm for this class of networks. [ABSTRACT FROM AUTHOR]