Serwis Infona wykorzystuje pliki cookies (ciasteczka). Są to wartości tekstowe, zapamiętywane przez przeglądarkę na urządzeniu użytkownika. Nasz serwis ma dostęp do tych wartości oraz wykorzystuje je do zapamiętania danych dotyczących użytkownika, takich jak np. ustawienia (typu widok ekranu, wybór języka interfejsu), zapamiętanie zalogowania. Korzystanie z serwisu Infona oznacza zgodę na zapis informacji i ich wykorzystanie dla celów korzytania z serwisu. Więcej informacji można znaleźć w Polityce prywatności oraz Regulaminie serwisu. Zamknięcie tego okienka potwierdza zapoznanie się z informacją o plikach cookies, akceptację polityki prywatności i regulaminu oraz sposobu wykorzystywania plików cookies w serwisie. Możesz zmienić ustawienia obsługi cookies w swojej przeglądarce.
We show how to decompose efficiently in parallel any graph into a number, $$\tilde \gamma$$ , of outerplanar subgraphs (called hammocks) satisfying certain separator properties. We achieve this decomposition in O(log n log log n) time using O(n + m) CREW PRAM processors, for an n-vertex, m-edge graph. This decomposition provides a general framework for solving graph problems efficiently in parallel...
We present here an algorithm for detecting (and outputting, if exists) a negative cycle in an n-vertex planar digraph G with real edge weights. Its running time ranges from O(n) up to O(n1.5 log n) as a certain topological measure of G varies from 1 up to Θ(n). Moreover, an efficient CREW PRAM implementation is given. Our algorithm applies also to digraphs whose genus γ is o(n).
We study the problem of bounding from above and below a given set of bit vectors by the set of satisfying truth assignments of a Horn formula. We point out a rather unexpected connection between the upper bounding problem and the problem of generating all transversals of a hypergraph, and settle several related complexity questions.
We study the complexity of telling whether a set of bitvectors represents the set of all satisfying truth assignments of a Boolean expression of a certain type. We show that the problem is coNP-complete when the expression is required to be in conjunctive normal form with three literals per clause (3CNF). We also prove a Dichotomy Theorem analogous to the classical one by Schaefer, stating that, unless...
In this paper, we present a randomized algorithm for a mobile agent to search for an item stored at a node t of a network, without prior knowledge of its exact location. Each node of the network has a database that will answer queries of the form “how do I find t?” by responding with the first edge on a shortest path to t. It may happen that some nodes, called liars, give bad advice. We investigate...
Podaj zakres dat dla filtrowania wyświetlonych wyników. Możesz podać datę początkową, końcową lub obie daty. Daty możesz wpisać ręcznie lub wybrać za pomocą kalendarza.