Skip to Main content Skip to Navigation
Conference papers

On Greedy Trie Execution

Abstract : In the paper "How to select a looser'' Prodinger was analyzing an algorithm where $n$ participants are selecting a leader by flipping fair 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 fair coin).
Keywords : Trie leader election
Complete list of metadata

Cited literature [7 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:54:51 PM
Last modification on : Tuesday, March 7, 2017 - 3:18:43 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:33:58 AM


Publisher files allowed on an open archive




Zbigniew Gołębiewski, Filip Zagórski. On Greedy Trie Execution. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12), 2012, Montreal, Canada. pp.377-380, ⟨10.46298/dmtcs.3007⟩. ⟨hal-01197231⟩



Record views


Files downloads