109 citations · 122 across the 7 of their papers we have counts for
7 papers
Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph
Stephan Mertens
We present an algorithm to compute the domination polynomial of the grid, cylinder, and torus graphs and the king graph. The time complexity of the algorithm is $O(m^2…
Domination by kings is oddly even
Cristopher Moore, Stephan Mertens
The king graph consists of all locations on an chessboard, where edges are legal moves of a chess king. %where each vertex represents a square on a chessb…
Domination Polynomial of the Rook Graph
Stephan Mertens
A placement of chess pieces on a chessboard is called dominating, if each free square of the chessboard is under attack by at least one piece. In this contribution we compute the n…
Parallel Complexity of Random Boolean Circuits
Jon Machta, Simon DeDeo, Stephan Mertens +1
Random instances of feedforward Boolean circuits are studied both analytically and numerically. Evaluating these circuits is known to be a P-complete problem and thus, in the worst…
Random Costs in Combinatorial Optimization
Stephan Mertens
The random cost problem is the problem of finding the minimum in an exponentially long list of random numbers. By definition, this problem cannot be solved faster than by exhaustiv…
On the VC-dimension of neural networks with binary weights
S. Mertens, A. Engel
We investigate the VC-dimension of the perceptron and simple two-layer networks like the committee- and the parity-machine with weights restricted to values . For binary inpu…