Aksen, Mark and Miklós, István and Zhou, Kathleen (2017) Half-regular factorizations of the complete bipartite graph. DISCRETE APPLIED MATHEMATICS, 230. pp. 21-33. ISSN 0166-218X
|
Text
1602.04316v1.pdf Download (459kB) | Preview |
Abstract
We consider a bipartite version of the color degree matrix problem. A bipartite graph G(U,V,E) is half-regular if all vertices in U have the same degree. We give necessary and sufficient conditions for a bipartite degree matrix (also known as demand matrix) to be the color degree matrix of an edge-disjoint union of half-regular graphs. We also give necessary and sufficient perturbations to transform realizations of a half-regular degree matrix into each other. Based on these perturbations, a Markov chain Monte Carlo method is designed in which the inverse of the acceptance ratios is polynomial bounded. Realizations of a half-regular degree matrix are generalizations of Latin squares, and they also appear in applied neuroscience. © 2017
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Graph theory; Matrix problem; Markov Chain Monte-Carlo; Markov Chain Monte Carlo method; Latin square; Degree sequence; Complete bipartite graphs; Bipartite graphs; Acceptance ratio; Monte Carlo methods; Matrix algebra; Markov processes; Inverse problems; FACTORIZATION; CHAINS; Markov chain Monte Carlo; latin squares; Graph factorization; Edge packing; Degree sequences; Degree matrix |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 30 Jan 2018 13:04 |
| Last Modified: | 30 Jan 2018 13:04 |
| URI: | http://real.mtak.hu/id/eprint/73578 |
Actions (login required)
 |
Edit Item |
