enter search term and/or author name
Upgrading Subgroup Triple-Product-Property Triples
Article No.: 1.1
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
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...
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
Article No.: 1.4
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
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...
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
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...