Temat: randomized algorithms - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks
Autorzy:: Formanowicz, P.
Tanaś, K.
Powiązania:: https://bibliotekanauki.pl/articles/331003.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Oficyna Wydawnicza
Tematy:: graf sześcienny
kolorowanie krawędzi
skojarzenie doskonałe
algorytm zrandomizowany
sieć komputerowa
cubic graph
edge colouring
perfect matching
randomized algorithms
computer networks
Opis:: It was conjectured by Fan and Raspaud (1994) that every bridgeless cubic graph contains three perfect matchings such that every edge belongs to at most two of them. We show a randomized algorithmic way of finding Fan-Raspaud colorings of a given cubic graph and, analyzing the computer results, we try to find and describe the Fan-Raspaud colorings for some selected classes of cubic graphs. The presented algorithms can then be applied to the pair assignment problem in cubic computer networks. Another possible application of the algorithms is that of being a tool for mathematicians working in the field of cubic graph theory, for discovering edge colorings with certain mathematical properties and formulating new conjectures related to the Fan-Raspaud conjecture.
Źródło:: International Journal of Applied Mathematics and Computer Science; 2012, 22, 3; 765-778
1641-876X
2083-8492
Pojawia się w:: International Journal of Applied Mathematics and Computer Science
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: Randomized and quantum algorithms for solving initial-value problems in ordinary differential equations of order k
Autorzy:: Goćwin, M.
Szczęsny, M.
Powiązania:: https://bibliotekanauki.pl/articles/255063.pdf
Data publikacji:: 2008
Wydawca:: Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie. Wydawnictwo AGH
Tematy:: k-th order initial-value problems
randomized computing
quantum computing
optimal algorithms
complexity
Opis:: The complexity of initial-value problems is well studied for systems of equations of first order. In this paper, we study the ε-complexity for initial-value problems for scalar equations of higher order. We consider two models of computation, the randomized model and the quantum model. We construct almost optimal algorithms adjusted to scalar equations of higher order, without passing to systems of first order equations. The analysis of these algorithms allows us to establish upper complexity bounds. We also show (almost) matching lower complexity bounds. The ε-complexity in the randomized and quantum setting depends on the regularity of the right-hand side function, but is independent of the order of equation. Comparing the obtained bounds with results known in the deterministic case, we see that randomized algorithms give us a speed-up by 1/2, and quantum algorithms by 1 in the exponent. Hence, the speed-up does not depend on the order of equation, and is the same as for the systems of equations of first order. We also include results of some numerical experiments which confirm theoretical results.
Źródło:: Opuscula Mathematica; 2008, 28, 3; 247-277
1232-9274
2300-6919
Pojawia się w:: Opuscula Mathematica
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "randomized algorithms" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język