Institut für Informatik
 
Abteilung V

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

13.07.2016

Complexity of Nondeterministic Graph Parameter Testing
(Revised Version)
Marek Karpinski, Roland Marko
[Download PostScript] [Download PDF]

We study the sample complexity of nondeterministically testable graph parameters and improve existing bounds on it by several orders of magnitude. The technique used would be also of independent interest. We also discuss the special case of weak nondeterministic testing for uniform hypergraphs of arbitrary order.

Last Change: 07/14/16 at 11:36:59
 English 		Universität Bonn -> Institut für Informatik -> Abteilung V