University of Twente Student Theses
Balancing balanceable matrices
Jong, J. de (2022) Balancing balanceable matrices.
|
PDF
877kB |
| Abstract: | Totally unimodular matrices play an important role in combinatorial optimization. Testing if a matrix is totally unimodular requires checking if a matrix can become balanced by multiplying a subset of the entries with $-1$. A matrix with all entries in $\{-1,0,1\}$ is balanced if in every submatrix with $2$ nonzero entries per row and per column, the sum of the entries is a multiple of $4$. This paper describes an improved algorithm to create a balanced signing and a linear time algorithm to create a balanced signing for graphic matrices. |
| Item Type: | Essay (Bachelor) |
| Faculty: | EEMCS: Electrical Engineering, Mathematics and Computer Science |
| Subject: | 31 mathematics |
| Programme: | Applied Mathematics BSc (56965) |
| Link to this item: | https://purl.utwente.nl/essays/89397 |
| Export this item as: | BibTeX EndNote HTML Citation Reference Manager |
Show download statistics for this publication
Show download statistics for this publicationRepository Staff Only: item control page