University of Twente Student Theses


Balancing balanceable matrices

Jong, J. de (2022) Balancing balanceable matrices.

[img] PDF
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:
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page