UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

The complexity of learning minor closed graph classes

Domingo, C; Shawe-Taylor, J; (1995) The complexity of learning minor closed graph classes. In: UNSPECIFIED (pp. 249-260).

Full text not available from this repository.

Abstract

© Springer-Verlag Berlin Heidelberg 1995. The paper considers the problem of learning classes of graphs closed under taking minors. It is shown that any such class can be properly learned in polynomial time using membership and equivalence queries. The representation of the class is in terms of a set of minimal excluded minors (obstruction set). Moreover, a negative result for learn­ing such classes using only equivalence queries is also provided, after introducing a notion of reducibility among query learning problems.

Type: Book chapter
Title: The complexity of learning minor closed graph classes
ISBN: 3540604545
ISBN-13: 9783540604549
UCL classification: UCL > Provost and Vice Provost Offices
UCL > Provost and Vice Provost Offices > UCL BEAMS
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science
UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science
URI: http://discovery.ucl.ac.uk/id/eprint/79115
Downloads since deposit
0Downloads
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item