For a graph G, OALG asks whether or not an input graph H together with a partial map g :S?G, SV(H), admits a homomorphism f :H?G such that f|S=g. We s...
We present a linear time algorithm to properly color the edges of any graph of maximum degree 3 using 4 colors. Our algorithm uses a greedy approach a...
We study the expected performance of Prim's minimum spanning tree (MST) algorithm implemented using ordinary heaps. We show that this implementation r...
