We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog(8)(n) logW) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight ...
详细信息
ISBN:
(纸本)9781665455190
We present a randomized algorithm that computes single-source shortest paths (SSSP) in O(mlog(8)(n) logW) time when edge weights are integral and can be negative. This essentially resolves the classic negative-weight SSSP problem. The previous bounds are (O) over tilde ((m + n(1.5)) logW) [BLNPSSSW FOCS'20] and m(4/3+o(1)) logW [AMV FOCS'20]. Near-linear time algorithms were known previously only for the special case of planar directed graphs [Fakcharoenphol and Rao FOCS'01]. In contrast to all recent developments that rely on sophisticated continuous optimization methods and dynamic algorithms, our algorithm is simple: it requires only a simple graph decomposition and elementary combinatorial tools. In fact, ours is the first combinatorial algorithm for negative-weight SSSP to break through the classic (O) over tilde (m root n logW) bound from over three decades ago [Gabow and Tarjan SICOMP'89].
Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vert...
详细信息
Given an undirected graph G with n vertices, the independent feedback vertex set problem is to find a vertex subset F of G with the minimum number of vertices such that F is both an independent set and a feedback vertex set of G, if it exists. This problem is known to be NP-hard for bipartite planar graphs of maximum degree four. In this paper, we study the approximability of the problem. We first show that, for any fixed epsilon > 0, unless P = NP, there exists no polynomial-time n(1)-epsilon-approximation algorithm even for bipartite planar graphs. We then give an alpha(Delta - 1)/2-approximation algorithm for bipartite graphs G of maximum degree Delta, which runs in t(alpha, G) + O (Delta n) time, under the assumption that there is an alpha-approximation algorithm for the original feedback vertex set problem on bipartite graphs which runs in t(alpha, G) time. This algorithmic result also yields a polynomial-time (exact) algorithm for the independent feedback vertex set problem on bipartite graphs of maximum degree three. (C) 2020 Elsevier B.V. All rights reserved.
This paper describes a new automatic layout algorithm named CoSEP for compound graphs with port constraints. The algorithm works by extending the physical model of a previous algorithm named CoSE by defining additiona...
详细信息
This paper describes a new automatic layout algorithm named CoSEP for compound graphs with port constraints. The algorithm works by extending the physical model of a previous algorithm named CoSE by defining additional force types and heuristics for constraining edges to connect to certain user-defined locations on end nodes. Similar to its predecessor, CoSEP also accounts for non-uniform node dimensions and arbitrary levels of nesting via compound nodes. Our experiments show that CoSEP significantly improves the quality of the layouts for compound graphs with port constraints with respect to commonly accepted graph drawing criteria while running reasonably fast, suitable for use in interactive applications for small to medium-sized (up to 500 nodes) graphs. A complete JavaScript implementation of CoSEP as a *** extension along with a demo page is freely available at .
A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put in the problem of findin...
详细信息
A central problem in graph mining is finding dense subgraphs, with several applications in different fields, a notable example being identifying communities. While a lot of effort has been put in the problem of finding a single dense subgraph, only recently the focus has been shifted to the problem of finding a set of densest subgraphs. An approach introduced to find possible overlapping subgraphs is the Top-k-Overlapping Densest Subgraphs problem. Given an integer k >= 1 and a parameter lambda > 0, the goal of this problem is to find a set of k dense subgraphs that may share some vertices. The objective function to be maximized takes into account the density of the subgraphs, the parameter lambda and the distance between each pair of subgraphs in the solution. The Top-k-Overlapping Densest Subgraphs problem has been shown to admit a 1/10-factor approximation algorithm. Furthermore, the computational complexity of the problem has been left open. In this paper, we present contributions concerning the approximability and the computational complexity of the problem. For the approximability, we present approximation algorithms that improve the approximation factor to 1/2, when k is smaller than the number of vertices in the graph, and to 2/3, when k is a constant. For the computational complexity, we show that the problem is NP-hard even when k = 3.
The spectral matching algorithm is a classic method for finding correspondences between two graphs, a fundamental task in pattern recognition. It has a time complexity of O(n4) and a space complexity of O(n4), where n...
详细信息
The existing Visual-inertial-LiDAR localization methods lack consideration of sensors degradation in challenging scene, such as underground space, where light condition is poor, text feature is scarce and geometric st...
详细信息
We study the Steiner k-eccentricity on trees, which generalizes the previous one in the paper [On the average Steiner 3-eccentricity of trees, arXiv:2005.10319]. We achieve much stronger properties for the Steiner k-e...
详细信息
We study the Steiner k-eccentricity on trees, which generalizes the previous one in the paper [On the average Steiner 3-eccentricity of trees, arXiv:2005.10319]. We achieve much stronger properties for the Steiner k-ecc tree than that in the previous paper. Based on this, a linear time algorithm is devised to calculate the Steiner k-eccentricity of a vertex in a tree. On the other hand, lower and upper bounds of the average Steiner k-eccentricity index of a tree on order nare established based on a novel technique which is quite different and also much easier to follow than the earlier one. (C) 2021 Elsevier B.V. All rights reserved.
In the Cluster Vertex Deletion problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results i...
详细信息
In the Cluster Vertex Deletion problem the input is a graph G and an integer k. The goal is to decide whether there is a set of vertices S of size at most k such that the deletion of the vertices of S from G results in a graph in which every connected component is a clique. We give an algorithm for Cluster Vertex Deletion whose running time is O*(1.811(k)).
Hierarchical graph pooling has shown great potential for capturing high-quality graph representations through the node cluster selection mechanism. However, the current node cluster selection methods have inadequate c...
详细信息
With the expansion of graph data in the real world, unsupervised graph representation learning shows greater potential. Unsupervised graph representation learning is mainly about extracting high-level representation f...
详细信息
暂无评论