Besonderhede van voorbeeld: 92510177700582229

English

In the first part we show that there are dense (directed) graphs having no nontrivial strong certificates for maintaining a depth-first search tree, hence the so-called sparsification technique cannot be applied effectively to this problem.

Hungarian

Egyrészt megmutattuk, hogy vannak olyan sűrű (irányított) gráfok, melyeknek nincs nemtriviális strong certificate-je a mélységi keresőfa nyilvántartására, így az úgynevezett sparsification technika nem alkalmazható erre a problémára.