3

Computing the Difficulty of Critical Bootstrap Percolation Models is NP-hard

Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three universality classes, the most studied being the 'critical' one. For this class the scaling of the quantity of …

Terminal-Pairability in Complete Bipartite Graphs with Non-Bipartite Demands

We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. In computer science, this problem is known as the …