Miklós, István and Erdős, Péter and Soukup, Lajos (2013) Towards random uniform sampling of bipartite graphs with given degree sequence. ELECTRONIC JOURNAL OF COMBINATORICS, 20 (1). ISSN 1077-8926
|
Text
MES-EJC13.pdf Download (585kB) | Preview |
Abstract
In this paper we consider a simple Markov chain for bipartite graphs with given degree sequence on n vertices. We show that the mixing time of this Markov chain is bounded above by a polynomial in n in case of half-regular degree sequence. The novelty of our approach lies in the construction of the multicommodity flow in Sinclair's method.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Regular graphs |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 06 Feb 2014 05:32 |
| Last Modified: | 08 Feb 2014 08:04 |
| URI: | http://real.mtak.hu/id/eprint/9898 |
Actions (login required)
 |
Edit Item |
