摘要 :
The traditional vulnerability parameter connectivity is the minimum number of nodes needed to be removed to disconnect a network. Likewise, edge connectivity is the minimum number of edges needed to be removed to disconnect. A dis...
展开
The traditional vulnerability parameter connectivity is the minimum number of nodes needed to be removed to disconnect a network. Likewise, edge connectivity is the minimum number of edges needed to be removed to disconnect. A disconnected network may still be viable if it contains a sufficiently large component. Component order connectivity and component order edge connectivity are the minimum number of nodes, respectively edges needed to be removed so that all components of the resulting network have order less than some preassigned threshold value. In this paper we survey some results of the component order connectivity models.
收起
摘要 :
Dr. Charles L. Suffel (1941-2021) was an influential mathematics educator and scholar at Stevens Institute of Technology for more than half a century. Managing Editor of Networks for 20 years, Suffel's reach extended far beyond th...
展开
Dr. Charles L. Suffel (1941-2021) was an influential mathematics educator and scholar at Stevens Institute of Technology for more than half a century. Managing Editor of Networks for 20 years, Suffel's reach extended far beyond the Stevens campus. He coauthored dozens of graph theory papers and mentored more than a dozen Ph.D. thesis students. In this article, we discuss his contributions to the field of network reliability theory and his legacy as a teacher and mentor.
收起
摘要 :
Given a graph G := (V, E) and an integer k >= 2, the component order edge connectivity of G is the smallest size of an edge set D such that the subgraph induced by G - D has all components of order less than k. Let G(n, m) denote ...
展开
Given a graph G := (V, E) and an integer k >= 2, the component order edge connectivity of G is the smallest size of an edge set D such that the subgraph induced by G - D has all components of order less than k. Let G(n, m) denote the collection of simple graphs G which have n vertices and m edges. In this paper we consider properties of component order edge connectivity for G(n, m). Particularly we prove properties of the maximum and minimum values of the component order edge connectivity for G(n,m) for specific values of n, m and k.
收起
摘要 :
We study the complexity of some algorithmic problems on directed hypergraphs and their strongly connected components (SCCs). The main contribution is an almost linear time algorithm computing the terminal strongly connected compon...
展开
We study the complexity of some algorithmic problems on directed hypergraphs and their strongly connected components (SCCs). The main contribution is an almost linear time algorithm computing the terminal strongly connected components (i.e. Sees which do not reach any components but themselves). Almost linear here means that the complexity of the algorithm is linear in the size of the hypergraph up to a factor a(n), where a is the inverse of Ackermann function, and n is the number of vertices. Our motivation to study this problem arises from a recent application of directed hypergraphs to computational tropical geometry. We also discuss the problem of computing all Sccs. We establish a superlinear lower bound on the size of the transitive reduction of the reachability relation in directed hypergraphs, showing that it is combinatorially more complex than in directed graphs. Besides, we prove a linear time reduction from the well-studied problem of finding all minimal sets among a given family to the problem of computing the SCCs. Only subquadratic time algorithms are known for the former problem. These results strongly suggest that the problem of computing the Sccs is harder in directed hypergraphs than in directed graphs.
收起
摘要 :
We consider the space of all composition operators, acting on the Hardy space over the unit disk, in the uniform operator topology. We obtain a characterization for linear connection between composition operators. As one of applic...
展开
We consider the space of all composition operators, acting on the Hardy space over the unit disk, in the uniform operator topology. We obtain a characterization for linear connection between composition operators. As one of applications, we see that the set of all compact composition operators is a polygonally connected component, in sharp contrast to the known fact that this set is properly contained in a path connected component. When the inducing maps have "good" boundary behavior in the sense of higher-order data and order of contact, we extend/recover the Kriete-Moorhouse characterization for linear connection through a completely different approach relying on our results. We also notice some results in conjunction with the Bergman space case. Several questions motivated by our results are included. (C) 2022 Elsevier Inc. All rights reserved.
收起
摘要 :
We say that an abelian variety over a p-adic field K has anisotropic reduction (AR) if the special fiber of its Neron minimal model does not contain a nontrivial split torus. This includes all abelian varieties with potentially go...
展开
We say that an abelian variety over a p-adic field K has anisotropic reduction (AR) if the special fiber of its Neron minimal model does not contain a nontrivial split torus. This includes all abelian varieties with potentially good reduction and, in particular, those with complex or quaternionic multiplication. We give a bound for the size of the K-rational torsion subgroup of a g-dimensional AR variety depending only on g and the numerical invariants of K (the absolute ramification index and the cardinality of the residue field). Applying these bounds to abelian varieties over a number field with everywhere locally anisotropic reduction, we get bounds which, as a function of g, are close to optimal. In particular, we determine the possible cardinalities of the torsion subgroup of an AR abelian surface over the rational numbers, up to a set of 11 values which are not known to occur. The largest such value is 72.
收起
摘要 :
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two a...
展开
We consider the problem of detecting a cycle in a directed graph that grows by arc insertions and the related problems of maintaining a topological order and the strong components of such a graph. For these problems, we give two algorithms, one suited to sparse graphs, the other to dense graphs. The former takes O(min{m(1/2), n(2/3)}m) time to insert m arcs into an n-vertex graph; the latter takes O(n(2) log n) time. Our sparse algorithm is substantially simpler than a previous O(m(3/2))-time algorithm; it is also faster on graphs of sufficient density. The time bound of our dense algorithm beats the previously best time bound of O(n(5/2)) for dense graphs. Our algorithms rely for their efficiency on vertex numberings weakly consistent with topological order: we allow ties. Bounds on the size of the numbers give bounds on running time.
收起
摘要 :
Kelmans, and later independently Bogdanowicz and Satyanarayana, Schoppmann, and Suffel, showed that a graph operation which has come to be known as the compression of C from vertex u to vertex v could not increase, and typically d...
展开
Kelmans, and later independently Bogdanowicz and Satyanarayana, Schoppmann, and Suffel, showed that a graph operation which has come to be known as the compression of C from vertex u to vertex v could not increase, and typically decreased, both the number of spanning trees and the all-terminal reliability of a graph. Both these quantities are well-known vulnerability parameters, i.e., measures of the strength of a network, and subsequently a number of other prominent vulnerability parameters - including vertex connectivity, toughness, scattering number, edge connectivity, edge toughness, and binding number - have been shown to be affected by compression in a similar way. As a consequence threshold graphs are extremal for all of the parameters mentioned. In this paper we show that for the graph vulnerability parameters integrity, tenacity, and k-component order connectivity, if u, v are adjacent then compression cannot increase, and typically decreases them. As a consequence, these parameters have quasi-threshold graphs as extremal graphs. We also show, however, that there are graphs with non-adjacent u, v where compression increases these parameters. To the best of our knowledge, these parameters are the first identified that behave differently under compression depending upon which pairs of vertices are used in the compression. (C) 2018 Elsevier B.V. All rights reserved.
收起
摘要 :
We characterize the development of intrinsic connectivity networks (ICNs) from 4 to 9 months of age with resting state magnetic resonance imaging performed on sleeping infants without sedative medication. Data is analyzed with ind...
展开
We characterize the development of intrinsic connectivity networks (ICNs) from 4 to 9 months of age with resting state magnetic resonance imaging performed on sleeping infants without sedative medication. Data is analyzed with independent component analysis (ICA). Using both low (30 components) and high (100 components) 1CA model ordtr decompositions, we find that the functional network connectivity (FNC) map is largely similar at both 4 and 9 months. However at 9 months the connectivity strength decreases within local networks and increases between more distant networks. The connectivity within the default-mode network, which contains both local and more distant nodes, also increases in strength with age. The low frequency power spectrum increases with age only in the posterior cingulate cortex and posterior default mode network. These findings are consistent with a general developmental pattern of increasing longer distance functional connectivity over the first year of life and raise questions regarding the developmental importance of the posterior cingulate at this age.
收起
摘要 :
Resting-state functional connectivity (FC) changes dynamically and major depressive disorder (MDD) has abnormality in functional connectivity networks (FCNs), but few existing resting-state fMRI study on MDD utilizes the dynamics,...
展开
Resting-state functional connectivity (FC) changes dynamically and major depressive disorder (MDD) has abnormality in functional connectivity networks (FCNs), but few existing resting-state fMRI study on MDD utilizes the dynamics, especially for identifying depressive individuals from healthy controls. In this paper, we propose a methodological procedure for differential diagnosis of depression, called HN3D. which is based on high-order functional connectivity networks (HFCN). Firstly, HN3D extracts time series by independent component analysis, and partitions them into overlapped short series by sliding time window. Secondly, it constructs a FCN for each time window and concatenates correlation matrices of all FCNs to generate correlation time series. Then, correlation time series are grouped into different clusters and high-order correlations for HFCN is calculated based on their means. Finally, graph based features of HFCNs are extracted and selected for a linear discriminative classifier. Tested on 21 healthy controls and 20 MDD patients, HN3D achieved its best 100% classification accuracy, which is much higher than results based on stationary FCNs. In addition, most discriminative components of HN3D locate in default mode network and visual network, which are consistent with existing stationary-based results on depression. Though HN3D needs to be studied further, it is helpful for the differential diagnosis of depression and might have potentiality in identifying relevant biomarkers.
收起
原文获取