|
|||||
 |
|
|
|
|
|
|
An algebraic
Monte-Carlo algorithm for the partition adjacency matrix
realization problem
Éva Czabarka, László Székely, Zoltán Toroczkai and Shanise Walker |
|
Vol. 12 (2021), No. 2, 115–124
|
|
DOI: 10.2140/astat.2021.12.115
|
Abstract |
|
The graphical realization of a given degree sequence and given partition adjacency matrix simultaneously, is a relevant problem in data driven modeling of networks. Here we formulate common generalizations of this problem and the exact matching problem, and solve them with an algebraic Monte-Carlo algorithm that runs in polynomial time if the number of partition classes is bounded by a constant. We note, that no deterministic polynomial time algorithm is known for any of these problems. |
Keywords
perfect matching, exact matching, degree sequence,
bipartite graph, Hall's theorem, joint degree matrix,
partition adjacency matrix, Monte-Carlo algorithm,
computational complexity
|
Mathematical Subject Classification 2010
Primary: 05D15
Secondary: 05C82, 05D40, 68W20
|
Milestones
Received: 29 September 2019
Revised: 7 April 2021
Accepted: 7 June 2021
Published: 13 December 2021
|
Authors |
| Éva Czabarka | |
| Department of Mathematics University of South Carolina Columbia, SC United States |
Visiting Professor Department of Pure and Applied Mathematics University of Johannesburg South Africa |
| László Székely | |
| Department of Mathematics University of South Carolina Columbia, SC United States |
Visiting Professor Department of Pure and Applied Mathematics University of Johannesburg South Africa |
| Zoltán Toroczkai | |
| Department of Physics, Department of
Computer Science and Engineering University of Notre Dame IN United States |
|
| Shanise Walker | |
| Department of Mathematics University of Wisconsin-Eau Claire WI United States |
|
