Recognition of generalized network matrices

In this 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×m can be tested for being binet in time O(n6m). 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-1N. Furthermore, we provide some results about Camion bases. For a matrix M of size n × 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(n2m') 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 {ε, ρ}-noncorelated network matrices, where ε and ρ are two given row indexes. It also results a polynomial recognition algorithm for these matrices.

Directeur(s):
Liebling, Thomas M.
Fukuda, Komei
Année
2007
Publisher:
Lausanne, EPFL
Mots-clefs:
Autres identifiants:
urn: urn:nbn:ch:bel-epfl-thesis3938-4
Laboratoires:

Note: Le statut de ce fichier est: Seulement EPFL

Notice créée le 2007-09-03, modifiée le 2019-03-16

Texte intégral / Full text:

PDF

Évaluer ce document:

1
2
3

(Pas encore évalué)