Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-APX-Reports 2014 Copyright 2014 University of Bonn, Department of Computer Science, 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
 Deutsch 		University of Bonn -> Department of Computer Science -> Chair V