ACM DL

Experimental Algorithmics (JEA)

Menu

Search Issue
enter search term and/or author name

Archive


Journal of Experimental Algorithmics (JEA), Volume 23 Issue 1, March 2018

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
DOI: 10.1145/3154835

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...

Graph Bisection with Pareto Optimization
Michael Hamann, Ben Strasser
Article No.: 1.2
DOI: 10.1145/3173045

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
DOI: 10.1145/3183350

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
DOI: 10.1145/3182656

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...