Computational complexity of combinatorial problems in specific graph classes

The topic of this diploma thesis is the edge distance labeling problem with specified parametres p, q and λ. We found a dychotomy for p = 2 and q = 1. So the problem is polynomial if λ ≤ 4 and it is NP-complete for λ > 4. The boundary is shifted by one prior to the vertex distance labeling problem, which has already been solved. Polynomial cases are characterized as some special paths and cycles with a few additional vertices. To show NP-completeness we use a well-known NP-complete problem of Monotone not all equal 3-SAT. That section has four parts: One for odd λ, one for even λ and two more reductions for λ = 5 and λ = 6.