enter search term and/or author name
Analysis of a High-Performance TSP Solver on the GPU
Jeffrey A. Robinson, Susan V. Vrbsky, Xiaoyan Hong, Brian P. Eddy
Article No.: 1.1
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...
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...
Complexity of Coloring Random Graphs: An Experimental Study of the Hardest Region
Zoltán Ádám Mann
Article No.: 1.3
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...
Dynamic Merging of Frontiers for Accelerating the Evaluation of Betweenness Centrality
Flavio Vella, Massimo Bernaschi, Giancarlo Carbone
Article No.: 1.4
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...