It is known that the problem of deciding k-colorability of a graph exhibits an easy-hard-easy pattern,—that is, the average-case complexity for backtrack-type algorithms, as a function of k, has a peak. This complexity peak is either at k = χ − 1 or k = χ, where χ is the chromatic number of the graph. However, the behavior around the complexity peak is poorly understood. In this article, we use list coloring to model coloring with a fractional number of colors between χ − 1 and χ. We present a comprehensive computational study on the complexity of backtrack-type graph coloring algorithms in this critical range. PubDate: Thu, 22 Mar 2018 00:00:00 GMT
Betweenness Centrality (BC) is a widely used metric of the relevance of a node in a network. The fastest-known algorithm for the evaluation of BC on unweighted graphs builds a tree representing information about the shortest paths for each vertex to calculate its contribution to the BC score. Actually, for specific vertices, the shortest-path trees of neighboring nodes could be leveraged to reduce the computational burden, but existing BC algorithms do not exploit that information and carry out redundant computations. We propose a new algorithm, called dynamic merging of frontiers, which makes use of such information to derive the BC score of degree-2 vertices by re-using the results of the sub-trees of the neighbors. PubDate: Thu, 22 Mar 2018 00:00:00 GMT
We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or node separators that optimize cut size and balance in the Pareto sense. Our core algorithm heuristically solves the balanced connected st-edge-cut problem, where two given nodes s and t must be separated by removing edges to obtain two connected parts. Using the core algorithm as a subroutine, we build variants that compute node separators that are independent of s and t. From the computed Pareto set, we can identify cuts with a particularly good tradeoff between cut size and balance that can be used to compute contraction and minimum fill-in orders, which can be used in Customizable Contraction Hierarchies (CCHs), a speed-up technique for shortest-path computations. PubDate: Mon, 12 Feb 2018 00:00:00 GMT
Abstract: Jeffrey A. Robinson, Susan V. Vrbsky, Xiaoyan Hong, Brian P. Eddy
Graphical Processing Units have been applied to solve NP-hard problems with no known polynomial time solutions. An example of such a problem is the Traveling Salesman Problem (TSP). The TSP is one of the most commonly studied combinatorial optimization problems and has multiple applications in the areas of engineering, transportation, and logistics. This article presents an improved algorithm for approximating the TSP on fully connected, symmetric graphs by utilizing the GPU. Our approach improves an existing 2-opt hill-climbing algorithm with random restarts by considering multiple updates to the current path found in parallel, and it allows k number of updates per iteration, called k-swap. PubDate: Wed, 10 Jan 2018 00:00:00 GMT
Subscription journal
[46 journals]
