Experimental Algorithmics (JEA)


Search Issue
enter search term and/or author name


Journal of Experimental Algorithmics (JEA), Volume 20, 2015

Section: Regular Papers

Upgrading Subgroup Triple-Product-Property Triples
Ivo Hedtke
Article No.: 1.1
DOI: 10.1145/2699877

In 2003, Cohn and Umans introduced a group-theoretic approach to fast matrix multiplication. This involves finding large subsets of a group satisfying the Triple Product Property (TPP) as a means to bound the exponent of matrix multiplication....

Upward Planarity Testing in Practice: SAT Formulations and Comparative Study
Markus Chimani, Robert Zeranski
Article No.: 1.2
DOI: 10.1145/2699875

A directed acyclic graph (DAG) is upward planar if it can be drawn without any crossings while all edges—when following them in their direction—are drawn with strictly monotonously increasing y-coordinates. Testing...

Degree Reduction in Labeled Graph Retrieval
Julian R. Ullmann
Article No.: 1.3
DOI: 10.1145/2699878

Within a given collection of graphs, a graph retrieval system may seek all graphs that contain a given graph, or may instead seek all graphs that are contained within a given graph. Although subgraph isomorphism is worst-case exponential, it may...

Weakening Cardinality Constraints Creates Harder Satisfiability Benchmarks
Ivor Spence
Article No.: 1.4
DOI: 10.1145/2746239

For some time, the satisfiability formulae that have been the most difficult to solve for their size have been crafted to be unsatisfiable by the use of cardinality constraints. Recent solvers have introduced explicit checking of such constraints,...

Dynamic Maintenance of a Shortest-Path Tree on Homogeneous Batches of Updates: New Algorithms and Experiments
Annalisa D'Andrea, Mattia D'Emidio, Daniele Frigioni, Stefano Leucci, Guido Proietti
Article No.: 1.5
DOI: 10.1145/2786022

A dynamic graph algorithm is called batch if it is able to update efficiently the solution of a given graph problem after multiple updates at a time (i.e., a batch) take place on the input graph. In this article, we study batch...

On Computing the Gromov Hyperbolicity
Nathann Cohen, David Coudert, Aurélien Lancin
Article No.: 1.6
DOI: 10.1145/2780652

The Gromov hyperbolicity is an important parameter for analyzing complex networks which expresses how the metric structure of a network looks like a tree. It is for instance used to provide bounds on the expected stretch of greedy-routing...

Clique Counting in MapReduce: Algorithms and Experiments
Irene Finocchi, Marco Finocchi, Emanuele G. Fusco
Article No.: 1.7
DOI: 10.1145/2794080

We tackle the problem of counting the number qk of k-cliques in large-scale graphs, for any constant k ≥ 3. Clique counting is essential in a variety of applications, including social network analysis. Our...