𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Sublinear-time algorithms for tournament graphs

✍ Scribed by Stefan Dantchev; Tom Friedetzky; Lars Nagel


Book ID
106407370
Publisher
Springer US
Year
2010
Tongue
English
Weight
446 KB
Volume
22
Category
Article
ISSN
1382-6905

No coin nor oath required. For personal study only.


πŸ“œ SIMILAR VOLUMES


Sublinear Time Algorithms
✍ Rubinfeld, Ronitt; Shapira, Asaf πŸ“‚ Article πŸ“… 2011 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 344 KB
Sublinear Geometric Algorithms
✍ Chazelle, Bernard; Liu, Ding; Magen, Avner πŸ“‚ Article πŸ“… 2005 πŸ› Society for Industrial and Applied Mathematics 🌐 English βš– 254 KB
Simple Markov-chain algorithms for gener
✍ Ravi Kannan; Prasad Tetali; Santosh Vempala πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 174 KB πŸ‘ 2 views

We consider two problems: randomly generating labeled bipartite graphs with a given degree sequence and randomly generating labeled tournaments with a given score sequence. We analyze simple Markov chains for both problems. For the first problem, we cannot prove that our chain is rapidly mixing in g