111355
20190717172514.0
doi
10.5075/epfl-thesis-3938
urn
urn:nbn:ch:bel-epfl-thesis3938-4
nebis
5419910
THESIS
eng
3938
Recognition of generalized network matrices
Lausanne
EPFL
2007
2007
183
Theses
Dominique de Werra, Jean Fonlupt, Michele Conforti
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.
network matrices
binet matrices and Camion bases
matrices réseau
matrices binet and bases de Camion.
(EPFLAUTH)167950
Musitelli, Antoine
167950
241744
Liebling, Thomas M.
dir.
105665
240750
Fukuda, Komei
dir.
107359
1635392
http://infoscience.epfl.ch/record/111355/files/EPFL_TH3938.pdf
Texte intégral / Full text
Texte intégral / Full text
252055
ROSO
oai:infoscience.tind.io:111355
DOI
thesis-bn2018
thesis
GLOBAL_SET
DOI2
SB
SB-SMA
IMA
EDMA
ROSO
2007-10-26
2007
3938/THESES
EPFL
PUBLISHED
THESIS