Back to Search
Start Over
On Greedy Trie Execution
- Source :
- Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AQ,..., Iss Proceedings (2012)
- Publication Year :
- 2012
- Publisher :
- Discrete Mathematics & Theoretical Computer Science, 2012.
-
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).
- Subjects :
- trie
leader election
[info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
[math.math-co] mathematics [math]/combinatorics [math.co]
[info.info-cg] computer science [cs]/computational geometry [cs.cg]
Mathematics
QA1-939
Subjects
Details
- Language :
- English
- ISSN :
- 13658050
- Volume :
- DMTCS Proceedings vol. AQ,...
- Issue :
- Proceedings
- Database :
- Directory of Open Access Journals
- Journal :
- Discrete Mathematics & Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.fea3b0cc034a94832d7dc720a5e9bb
- Document Type :
- article
- Full Text :
- https://doi.org/10.46298/dmtcs.3007