For certain computational models, a constant-factor time hierarchy theorem is known, showing that a constant-factor difference in time bounds makes a...

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find...

In this paper, we give a relatively simple though very efficient way to color the d-dimensional grid G(n1,n2,…,nd) (with ni vertices in each dimension...

In the minimum linear arrangement problem one wishes to assign distinct integers to the vertices of a given graph so that the sum of the differences (...

We derive a sound program for computing the semi-sum of two integers using only integer operators and without incurring overflow.