<abstract xmlns="http://www.w3.org/1999/xhtml">The authors in the paper <xref ref-type="bibr" rid="j_ausi-2018-0010_ref_015_w2aab3b7b2b1b6b1ab1ac15Aa">[15]</xref> presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly all the simple bipartite realizations whenever A is a bipartite degree sequence of a simple graph. The running time of both algorithms is 𝒪(m),where <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausi-2018-0010_eq_001.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mtext>m</mtext><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><msubsup><mo>∑</mo><mrow><mtext>i</mtext><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mrow><msub><mrow><mtext>a</mtext></mrow><mtext>i</mtext></msub></mrow></mrow></math><tex-math>${\rm{m}} = {1 \over 2}\sum\nolimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$</tex-math></alternatives></inline-formula>. Let A =(A1 : A2 : ... : Ak) be a <bold>k</bold>-partite degree sequence of a simple graph, where Ai has ni entries such that ∑ni=n. In the present article, we give a generalized algorithm that generates uniformly all the k-partite realizations of A and another algorithm that generates uniformly all the simple k-partite realizations of A. The running time of both algorithms is 𝒪(m), where <inline-formula><alternatives><inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" xlink:href="graphic/j_ausi-2018-0010_eq_002.png"></inline-graphic><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mi>m</mi><mo>=</mo><mfrac><mn>1</mn><mn>2</mn></mfrac><msubsup><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mi>n</mi></msubsup><mrow><msub><mrow><mi>a</mi></mrow><mi>i</mi></msub></mrow></mrow></math><tex-math>$m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}}$</tex-math></alternatives></inline-formula>.</abstract>

The authors in the paper [15] presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly all the simple bipartite realizations whenever A is a bipartite degree sequence of a simple graph. The running time of both algorithms is 𝒪(m),where m=12∑i=1nai${\rm{m}} = {1 \over 2}\sum\nolimits_{\rm {i} = 1}^n {{ \rm{a}_\rm {i}}}$. Let A =(A1 : A2 : ... : Ak) be a k-partite degree sequence of a simple graph, where Ai has ni entries such that ∑ni=n. In the present article, we give a generalized algorithm that generates uniformly all the k-partite realizations of A and another algorithm that generates uniformly all the simple k-partite realizations of A. The running time of both algorithms is 𝒪(m), where m=12∑i=1nai$m = {1 \over 2}\sum\nolimits_{i = 1}^n {{a_i}}$.

Sampling k-partite graphs with a given degree sequence

Department of Mathematics and Computer Science

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Sampling k-partite graphs with a given degree sequence"}

The authors in the paper [15] presented an algorithm that generates uniformly all the bipartite realizations and the other algorithm that generates uniformly...

Sampling k-partite graphs with a given degree sequence

Publié en ligne: 31 déc. 2018

Pages: 183 - 217

Reçu: 22 oct. 2018

DOI: https://doi.org/10.2478/ausi-2018-0010

Mots clés
Degree sequence, contraction of a degree sequence, degree sequence bipartition, contraction of a graph, deletion of a graph, ecological occurrence matrix

© 2018 Koko K. Kayibi et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Sampling k-partite graphs with a given degree sequence

Publié en ligne: 31 déc. 2018

Pages: 183 - 217

Reçu: 22 oct. 2018

DOI: https://doi.org/10.2478/ausi-2018-0010

Mots clésDegree sequence, contraction of a degree sequence, degree sequence bipartition, contraction of a graph, deletion of a graph, ecological occurrence matrix

© 2018 Koko K. Kayibi et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Mots clés
Degree sequence, contraction of a degree sequence, degree sequence bipartition, contraction of a graph, deletion of a graph, ecological occurrence matrix