000111355 001__ 111355
000111355 005__ 20190717172514.0
000111355 0247_ $$2doi$$a10.5075/epfl-thesis-3938
000111355 02470 $$2urn$$aurn:nbn:ch:bel-epfl-thesis3938-4
000111355 02471 $$2nebis$$a5419910
000111355 037__ $$aTHESIS
000111355 041__ $$aeng
000111355 088__ $$a3938
000111355 245__ $$aRecognition of generalized network matrices
000111355 269__ $$a2007
000111355 260__ $$bEPFL$$c2007$$aLausanne
000111355 300__ $$a183
000111355 336__ $$aTheses
000111355 502__ $$aDominique de Werra, Jean Fonlupt, Michele Conforti
000111355 520__ $$aIn 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.
000111355 6531_ $$anetwork matrices
000111355 6531_ $$abinet matrices and Camion bases
000111355 6531_ $$amatrices réseau
000111355 6531_ $$amatrices binet and bases de Camion.
000111355 700__ $$0(EPFLAUTH)167950$$g167950$$aMusitelli, Antoine
000111355 720_2 $$aLiebling, Thomas M.$$edir.$$g105665$$0241744
000111355 720_2 $$aFukuda, Komei$$edir.$$g107359$$0240750
000111355 8564_ $$zTexte intégral / Full text$$yTexte intégral / Full text$$uhttps://infoscience.epfl.ch/record/111355/files/EPFL_TH3938.pdf$$s1635392
000111355 909C0 $$pROSO$$0252055
000111355 909CO $$pthesis$$pthesis-bn2018$$pDOI$$ooai:infoscience.tind.io:111355$$qDOI2$$qGLOBAL_SET
000111355 918__ $$dEDMA$$bSB-SMA$$cIMA$$aSB
000111355 919__ $$aROSO
000111355 920__ $$b2007$$a2007-10-26
000111355 970__ $$a3938/THESES
000111355 973__ $$sPUBLISHED$$aEPFL
000111355 980__ $$aTHESIS