NeuroCOLT: Neural Networks and Computational Learning Theory

NeuroCOLT

Neural Networks and Computational Learning Theory

1994	1995
1996	1997
1998	1999
2000	2001

Books

info@neurocolt.org

NeuroCOLT Technical Report NC-TR-94-014

Learning Minor Closed Graph Classes with Membership and Equivalence Queries

John Shawe-Taylor
Dept of Computer Science
Royal Holloway, University of London

Carlos Domingo
Department of Software
U. Politécnica de Catalunya

Hans Bodlaender
Dept of Computer Science
Utrecht University

James Abello
Computer Science Dept
Texas A&M University

Abstract
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).

Download Compressed Postscript