I know that there are some problems that are very hard to solve in general, but become much easier and asymptotically faster if restricted to only integer values.
One such example would be sorting which can be done in O(n+M) if only integer values are allowed.
Another example (I think) is the undirected single source shortest path problem which seems to be solvable in linear time if all weights are positive integers.
My question now is which problems are significantly easier to solve if restricted to integer values (and why?)
Note: I obviously don't expect a complete listing, I just want to understand the general principle behind the speed up by restricting the problem space to integers.