The Complexity of learning minor closed graph classes

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/82263

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Domingo Soriano, Carlos
dc.contributor.author	Shawe-Taylor, J
dc.date	1995-04
dc.identifier.citation	Domingo, C., Shawe-Taylor, J. "The Complexity of learning minor closed graph classes". 1995.
dc.identifier.uri	http://hdl.handle.net/2117/82263
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica
dc.subject	Complexity
dc.subject	Learning classes of graphs
dc.title	The Complexity of learning minor closed graph classes
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.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). Moreover, a negative result for learning such classes using only equivalence queries is also provided, after introducing a notion of reducibility between query learning problems.