Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-APX-Reports 2014 Copyright 2014 Universität Bonn, Institut für Informatik, Abt. V
89155

14.08.2014

Complexity of Nondeterministic Graph Parameter Testing
Marek Karpinski and Roland Marko
[Download PostScript] [Download PDF]

We study the sample complexity of nondeterministically testable graph parameters and improve existing bounds by several orders of magnitude. The technique used would be also of independent interest. We also discuss some generalization and the special case of nondeterministic testing with polynomial sample size.

Last Change: 11/05/14 at 11:05:39
 English 		Universität Bonn -> Institut für Informatik -> Abteilung V