Geodesic
On Greedy Trie Execution
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012).

Voir la notice de l'article provenant de la source Episciences

In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping <underline>fair</underline> coins, where recursively, the 0-party (those who i.e. have tossed heads) continues until the leader is chosen. We give an answer to the question stated in the Prodinger's paper – what happens if not a 0-party is recursively looking for a leader but always a party with a smaller cardinality. We show the lower bound on the number of rounds of the greedy algorithm (for <underline>fair</underline> coin). 
@article{DMTCS_2012_special_262_a28,
     author = {Go{\l}\k{e}biewski, Zbigniew and Zag\'orski, Filip},
     title = {On {Greedy} {Trie} {Execution}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)},
     year = {2012},
     doi = {10.46298/dmtcs.3007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3007/}
}
TY  - JOUR
AU  - Gołębiewski, Zbigniew
AU  - Zagórski, Filip
TI  - On Greedy Trie Execution
JO  - Discrete mathematics & theoretical computer science
PY  - 2012
VL  - DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3007/
DO  - 10.46298/dmtcs.3007
LA  - en
ID  - DMTCS_2012_special_262_a28
ER  - 
%0 Journal Article
%A Gołębiewski, Zbigniew
%A Zagórski, Filip
%T On Greedy Trie Execution
%J Discrete mathematics & theoretical computer science
%D 2012
%V DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3007/
%R 10.46298/dmtcs.3007
%G en
%F DMTCS_2012_special_262_a28
Gołębiewski, Zbigniew; Zagórski, Filip. On Greedy Trie Execution. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12) (2012). doi : 10.46298/dmtcs.3007. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3007/

Cité par Sources :