Search ACM DL

Search Issue

enter search term and/or author name

**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 *q _{k}* of