Algorithms for learning and teaching sets of vertices in graphs

Details Algorithms for learning and teaching sets of vertices in graphs Algorithms for learning and teaching sets of vertices in graphs

1994-11-22

arxiv.org/abs/math/9411223v1

Mathematics

Combinatorics

11 pages

Scientific paper

The learning complexity of special sets of vertices in graphs is studied in the model(s) of exact learning by (extended) equivalence and membership queries. Polynomial-time learning algorithms are described for vertex covers, independent sets, and dominating sets. The complexity of learning vertex sets of fixed size is also investigated, and it is shown that the k-element vertex covers in a graph can be learned in a number of rounds of interaction that is independent of the size of the graph. Apart from the elegance of these algorithmic problems, the chief motivation is the surprising recently established connection between the important unsolved problem of the learning complexity of CNF (or DNF) formulas and the learning complexity of dominating sets. The complexity of teaching sets of vertices in graphs is also considered.

Affiliated with

Also associated with

No associations

Rating

Algorithms for learning and teaching sets of vertices in graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Algorithms for learning and teaching sets of vertices in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithms for learning and teaching sets of vertices in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-447548