Mathematics – Combinatorics
Scientific paper
2008-07-22
Mathematics
Combinatorics
183 pages
Scientific paper
In this PhD thesis, we deal with binet matrices, an extension of network matrices. The main result of this thesis is the following. A rational matrix A of size n times m can be tested for being binet in time O(n^6 m). If A is binet, our algorithm outputs a nonsingular matrix B and a matrix N such that [B N] is the node-edge incidence matrix of a bidirected graph (of full row rank) and A=B^{-1} N. Furthermore, we provide some results about Camion bases. For a matrix M of size n times m', we present a new characterization of Camion bases of M, whenever M is the node-edge incidence matrix of a connected digraph (with one row removed). Then, a general characterization of Camion bases as well as a recognition procedure which runs in O(n^2m') are given. An algorithm which finds a Camion basis is also presented. For totally unimodular matrices, it is proven to run in time O((nm)^2) where m=m'-n. The last result concerns specific network matrices. We give a characterization of nonnegative {r,s}-noncorelated network matrices, where r and s are two given row indexes. It also results a polynomial recognition algorithm for these matrices.
Musitelli Antoine
No associations
LandOfFree
Recognition of generalized network matrices 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 Recognition of generalized network matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Recognition of generalized network matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-436558