Search

Given an undirected graph and two pairs of vertices (si, ti) for i ∈{ 1, 2\} we show that there is a polynomial time Monte Carlo algorithm that finds disjoint paths of smallest total length joining si and ti for i ∈{ 1, 2\}, respectively, or concludes that there most likely are no such paths at all. Our algorithm applies to both the vertex- and edge-disjoint versions of the problem. Our algorithm is algebraic and uses permanents over the polynomial ring Z4[X] in combination with the isolation lemma of Mulmuley, Vazirani, and Vazirani to detect a solution. To this end, we develop a fast algorithm for permanents over the ring Zt[X], where t is a power of 2, by modifying Valiant's 1979 algorithm for the permanent over Zt. [ABSTRACT FROM AUTHOR]

We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of edges. Our algorithm is randomized and it takes expected amortized O(log n) time for each edge update, where n is the number of vertices in the graph. Moreover, for any sequence of t edge updates, the total time taken by the algorithm is O(t log n+n log² n) with high probability. [ABSTRACT FROM AUTHOR]

We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every 4-edge-connected graph G and every r \in V (G), there is a set of four spanning trees of G with the following property. For every vertex in G, the unique paths back to r in each tree are edge-disjoint. Our proof implies a polynomial-time algorithm for constructing the trees. [ABSTRACT FROM AUTHOR]

Let G be an interval graph and take one of its vertices x. Can we find in linear time a minimum number of vertex disjoint paths of G which cover the vertex set of G and have x as one of their endpoints? This paper provides a positive answer to this problem. In the course of developing such an algorithm, we explore the possibility of getting insight on the path structure of interval graphs via greedy graph searches. [ABSTRACT FROM AUTHOR]

Given a finite graph (network), let every node (cell) represent an individual dynamics given by a system of ordinary differential equations, and every arrow (edge) encode the dynamical influence of the tail node on the head node. We have then defined a coupled cell system that is associated with the given network structure. Subspaces that are defined by equalities of cell coordinates and left invariant under every coupled cell system respecting the network structure are called synchrony subspaces. They are completely determined by the network structure and form a complete lattice under set inclusions. We analyze the transition of the lattice of synchrony subspaces of a network that is caused by structural changes in the network topology, such as deletion and addition of cells or edges, and rewirings of edges. We give sufficient, and in some cases both sufficient and necessary, conditions under which lattice elements persist or disappear. [ABSTRACT FROM AUTHOR]

One of the most relevant tasks in network analysis is the detection of community structures, or clustering. Most popular techniques for community detection are based on the maximization of a quality function called modularity, which in turn is based upon particular quadratic forms associated to a real symmetric modularity matrix M, defined in terms of the adjacency matrix and a rank-one null model matrix. That matrix could be posed inside the set of relevant matrices involved in graph theory, alongside adjacency and Laplacian matrices. In this paper we analyze certain spectral properties of modularity matrices, which are related to the community detection problem. In particular, we propose a nodal domain theorem for the eigenvectors of M; we point out several relations occurring between the graph's communities and nonnegative eigenvalues of M; and we derive a Cheeger-type inequality for the graph modularity. [ABSTRACT FROM AUTHOR]