We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: { O(mn/log n) if m > n log n log log log n...
详细信息
We revisit the all-pairs-shortest-paths problem for an unweighted undirected graph with n vertices and m edges. We present new algorithms with the following running times: { O(mn/log n) if m > n log n log log log n O(mn log log n/log n) if m> n log log n O(n2log2logn/logn) if m <= n log log n. These represent the best time bounds known for the problem for all m << n(1.376). We also obtain a similar type of result for the diameter problem for unweighted directed graphs.
We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(root nm log L)/ B + MST(n, m)) on graphs with n vertices, m edges, and arbit...
详细信息
We present I/O-efficient single-source shortest path algorithms for undirected graphs. Our main result is an algorithm with I/O complexity O(root nm log L)/ B + MST(n, m)) on graphs with n vertices, m edges, and arbitrary edge lengths between 1 and L;MST(n, m) denotes the I/O complexity of computing a minimum spanning tree;B denotes the disk block size. If the edge lengths are drawn uniformly at random from ( 0, 1], the expected I/O complexity of the algorithm is O(root nm/ B + ( m/ B) log B + MST(n, m)). A simpler algorithm has expected I/O complexity O(root nm log B)/ B + MST(n, m) for uniformly random edge lengths.
We consider testing directed graphs Eulerianity in the orientation model introduced in Halevy et al. [2005]. Despite the local nature of the Eulerian property, it turns out to be significantly harder to test than othe...
详细信息
We consider testing directed graphs Eulerianity in the orientation model introduced in Halevy et al. [2005]. Despite the local nature of the Eulerian property, it turns out to be significantly harder to test than other properties studied in the orientation model. We show a nonconstant lower bound on the query complexity of 2-sided tests and a linear lower bound on the query complexity of 1-sided tests for this property. On the positive side, we give several 1-sided and 2-sided tests, including a sublinear query complexity 2-sided test, for general graphs. For special classes of graphs, including bounded-degree graphs and expander graphs, we provide improved results. In particular, we give a 2-sided test with constant query complexity for dense graphs, as well as for expander graphs with a constant expansion parameter.
We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an impl...
详细信息
We give experimental and theoretical results on the problem of computing the treewidth of a graph by exact exponential-time algorithms using exponential space or using only polynomial space. We first report on an implementation of a dynamic programming algorithm for computing the treewidth of a graph with running time O*(2(n)). This algorithm is based on the old dynamic programming method introduced by Held and Karp for the TRAVELING SALESMAN problem. We use some optimizations that do not affect the worst case running time but improve on the running time on actual instances and can be seen to be practical for small instances. We also consider the problem of computing TREEWIDTH under the restriction that the space used is only polynomial and give a simple O*(4(n)) algorithm that requires polynomial space. We also show that with a more complicated algorithm using balanced separators, TREEWIDTH can be computed in O*(2.9512(n)) time and polynomial space.
Transport processes on spatial networks are representative of a broad class of real world systems which, rather than being independent, are typically interdependent. We propose a measure of utility to capture key feat...
详细信息
Transport processes on spatial networks are representative of a broad class of real world systems which, rather than being independent, are typically interdependent. We propose a measure of utility to capture key features that arise when such systems are coupled together. The coupling is defined in a way that is not solely topological, relying on both the distribution of sources and sinks, and the method of route assignment. Using a toy model, we explore relevant cases by simulation. For certain parameter values, a picture emerges of two regimes. The first occurs when the flows go from many sources to a small number of sinks. In this case, network utility is largest when the coupling is at its maximum and the average shortest path is minimized. The second regime arises when many sources correspond to many sinks. Here, the optimal coupling no longer corresponds to the minimum average shortest path, as the congestion of traffic must also be taken into account. More generally, results indicate that coupled spatial systems can give rise to behavior that relies subtly on the interplay between the coupling and randomness in the source-sink distribution.
The well-known Brooksʼ Theorem says that each graph G of maximum degree k ⩾ 3 is k -colorable unless G = K k + 1 . We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.
The well-known Brooksʼ Theorem says that each graph G of maximum degree k ⩾ 3 is k -colorable unless G = K k + 1 . We generalize this theorem by allowing higher degree vertices with prescribed types of neighborhood.
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solvi...
详细信息
ISBN:
(纸本)9781611972108
Computing the winning set for Buchi objectives in alternating games on graphs is a central problem in computer aided verification with a large number of applications. The long standing best known upper bound for solving the problem is O{top}~(n·m), where n is the number of vertices and m is the number of edges in the graph. We are the first to break the O{top}~(n·m) boundary by presenting a new technique that reduces the running time to O(n~2). This bound also leads to O(n~2) time algorithms for computing the set of almost-sure winning vertices for Buchi objectives (1) in alternating games with probabilistic transitions (improving an earlier bound of {top}O(n·m)), (2) in concurrent graph games with constant actions (improving an earlier bound of O(n~3)), and (3) in Markov decision processes (improving for m ＞ n~(4/3) an earlier bound of O(min(m~(1.5),m· n~(2/3))). We also show that the same technique can be used to compute the maximal end-component decomposition of a graph in time O(n~2), which is an improvement over earlier bounds for m ＞ n~(4/3). Finally, we show how to maintain the winning set for Buchi objectives in alternating games under a sequence of edge insertions or a sequence of edge deletions in O(n) amortized time per operation. This is the first dynamic algorithm for this problem.
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to ...
详细信息
We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs. We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in 1,...,M, it runs in (O) over tilde(root Mn(omega+3)/2) time where omega < 2.376 is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in <(O)over tilde>(Mn(omega)t) time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of epsilon in (O) over tilde (n((omega+6)/3)) time. (C) 2011 Elsevier B.V. All rights reserved.
This paper presents the ideas, experiments and specifications related to the Supervised TextRank (STR) technique, a word tagging method based on the TextRank algorithm. The main innovation of STR technique is the use ...
详细信息
This paper presents the ideas, experiments and specifications related to the Supervised TextRank (STR) technique, a word tagging method based on the TextRank algorithm. The main innovation of STR technique is the use of a graph-based ranking algorithm similar to PageRank in a supervised fashion, gathering the information needed to build the graph representations of the text from a tagged corpus. We also propose a flexible graph specification language that allows to easily experiment with multiple configurations for the topology of the graph and for the information associated to the nodes and the edges. We have carried experiments in the Part-Of-Speech task, a common tagging problem in Natural Language Processing. In our best result we have achieved a precision of 96.16%, at the same level of the best tagging tools.
In this paper a new mixed nodal-mesh formulation of the PEEC method is proposed. Based on the hypothesis that charges reside only on the surface of conductors and that current density is solenoidal inside them, a nove...
详细信息
ISBN:
(纸本)9781424416998
In this paper a new mixed nodal-mesh formulation of the PEEC method is proposed. Based on the hypothesis that charges reside only on the surface of conductors and that current density is solenoidal inside them, a novel scheme is developed fully exploiting the physical properties of charges and currents. It comes out that the presented approach allows to reduce the number of unknowns while preserving the accuracy. An elegant and efficient algorithm, based on graph theory, is proposed to automatically search independent loops on three dimensional rectangular grids such as those arising in volumetric PEEC formulation. The method is validated through numerical results that confirm the accuracy of the proposed formulation from DC-to-daylight and its capability to provide memory saving.
暂无评论