## Oded Goldreich

## Abstract of M.Sc Thesis (Technion, 1982)

### Title: On the Complexity of Some Edge Testing Problems

Let G(V,E) be an undirected graph which describes the structure of
a communication network. During the maintenance period every line must
be tested in each of the two possible directions. A line is tested by
assigning one of its end-points to be a transmitter, the other to be
a receiver and sending a message from the transmitter to the receiver
through the line.

We define axiomatically 12 different models for communication networks
all subject to the two following axioms: a vertex cannot act as a
transmitter and as a receiver simultaneously and a vertex cannot
receive through two lines simultaneously. In each of the models two
problems arise: "What is the maximum number of lines one can test
simultaneously?" and "What is the minimum number of phases necessary for
testing the entire network?", where by a "phase" we mean a period in
which some tests are conducted simultaneously.

We show that in 8 of the above models, including the "natural"
model of radio communication, both problems are NP-Hard. In 3 other
models the problems can be solved by reducing them to either a maximum
matching problem or to an edge coloring problem; for 5 of the 6 resulting
problems, polynomial algorithms are known while for the remaining
problem the complexity is unknown. In the remaining model both problems
are trivial.

Finally, we consider two additional topics concerning the minimization
problems; the question of the gap between the lower bound and the upper
bound for these problems and the failure of the greedy approach to
solve them.

*Submitted to the Senate of the Technion, February 1982.*

#### Material available on-line

A
related
paper, 1984.

Back to Oded Goldreich's homepage.