Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: randomized algorithms

Sortuj według:

Ogranicz wyniki do:

The Fan-Raspaud conjecture: A randomized algorithmic approach and application to the pair assignment problem in cubic networks

Formanowicz P., Tanaś K.

International Journal of Applied Mathematics and Computer Science

2012

Vol. 22, no. 3

765-778

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.

Randomized enumeration

Dembiński P.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

1998

nr 848

1-17

W pracy zaproponowano probabilistyczną wersję rozproszonego algorytmu numeracji węzłów sieci procesów. Zaletą tego probabilistycznego podejścia jest to, że wynikowy algorytm poprawnie numeruje węzły sieci o dowolnej topologii i może być całkowicie asynchroniczny (w przypadku deterministycznych rozwiązań obie te cechy mają pewne ograniczenia). Przebadano zarówno poprawność zaproponowanego algorytmu jak i jego efektywność. Te ostatnią szacuje sie poprzez oczekiwaną liczbę 'rund', w terminach których zdefiniowano algorytm. Okazuje się, że ta oczekiwana wartość jest bliska jedynce, a to znaczy, że czas wykonania algorytmu jest w praktyce równy maksymalnemu czasowi przepływu informacji pomiędzy węzłami rozpatrywanej sieci. Algorytm został opisany w języku specyfikacji Estelle. Eksperymenty symulacyjne (wykonywane zarówno dla deterministycznych jak i probabilistycznych specyfikacji algorytmu w tym formalizmie) potwierdziły otrzymane rezultaty.

The paper describes a randomized version of the distributed enumeration algorithm (protocol) in a network of processes. The advantage of the randomized approach is in that the resulting algorithm works for all network topologies and for fully asynchronous communication (which is not the case for the deterministic case). Correctness of the protocol is examined as well its efficiency. The latter is estimated in probabilistic terms by means of the expected number of 'drawing rounds' in which the algorithm is defined. The value is shown to be close to one and it means that practically the algorithm is performed in time needed to broadcast a message in the network. The algorithm is implemented in the specification language Estelle. Simulation experiments (with both deterministic and randomized Estelle specifications) confirmed the obtained results.

Randomized enumeration

Dembiński P.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

1998

nr 848

1-17