On the Complexity of Timetable and Multi-Commodity Flow Problems

Shimon Even Alon Itai Adi Shamir

Published in: FOCS (1975)

Keyphrases

decision problems
benchmark problems
difficult problems
artificial intelligence
computational issues
information systems
computational complexity
feature space
lower bound
search space
optimization problems
np complete
application domains
practical problems
np hardness
polynomial hierarchy