Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2603.11478 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912963027271680 |
|---|---|
| author | Sun, Tong Hao, Jianshu Fu, Michael C. Jiang, Guangxin |
| author_facet | Sun, Tong Hao, Jianshu Fu, Michael C. Jiang, Guangxin |
| contents | We study the problem of generating graphs with prescribed degree sequences for bipartite, directed, and undirected networks. We first propose a sequential method for bipartite graph generation and establish a necessary and sufficient interval condition that characterizes the admissible number of connections at each step, thereby guaranteeing global feasibility. Based on this result, we develop bipartite graph enumeration and sampling algorithms suitable for different problem sizes. We then extend these bipartite graph algorithms to the directed and undirected cases by incorporating additional connection constraints, as well as feasibility verification and symmetric connection steps, while preserving the same algorithmic principles. Finally, numerical experiments demonstrate the performance of the proposed algorithms, particularly their scalability to large instances where existing methods become computationally prohibitive. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_11478 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Graph Generation Methods under Partial Information Sun, Tong Hao, Jianshu Fu, Michael C. Jiang, Guangxin Methodology Data Structures and Algorithms We study the problem of generating graphs with prescribed degree sequences for bipartite, directed, and undirected networks. We first propose a sequential method for bipartite graph generation and establish a necessary and sufficient interval condition that characterizes the admissible number of connections at each step, thereby guaranteeing global feasibility. Based on this result, we develop bipartite graph enumeration and sampling algorithms suitable for different problem sizes. We then extend these bipartite graph algorithms to the directed and undirected cases by incorporating additional connection constraints, as well as feasibility verification and symmetric connection steps, while preserving the same algorithmic principles. Finally, numerical experiments demonstrate the performance of the proposed algorithms, particularly their scalability to large instances where existing methods become computationally prohibitive. |
| title | Graph Generation Methods under Partial Information |
| topic | Methodology Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.11478 |