Mathematics – Combinatorics
Scientific paper
2009-01-07
Discrete Mathematics, Volume 309, Issue 16, 28 August 2009, Pages 5024-5042
Mathematics
Combinatorics
27 pages, 10 figures, under revision Discrete Mathematics
Scientific paper
10.1016/j.disc.2009.03.010
Seymour's famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called $k$-sums starting from network matrices and their transposes and two compact representation matrices $B_{1}, B_{2}$ of a certain ten element matroid. Given that $B_{1}, B_{2}$ are binet matrices we examine the $k$-sums of network and binet matrices. It is shown that the $k$-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for $k=2,3$. A new class of matrices is introduced the so called {\em tour matrices}, which generalises network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under $k$-sums, as well as under pivoting and other elementary operations on its rows and columns. Given the constructive proofs of the above results regarding the $k$-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.
Appa G.
Kotnyek B.
Papalamprou Konstantinos
Pitsoulis Leonidas
No associations
LandOfFree
On the representability of totally unimodular matrices on bidirected graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the representability of totally unimodular matrices on bidirected graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the representability of totally unimodular matrices on bidirected graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-720529