Estrutura grafica de matrizes (1990)
- Autores:
- Autor USP: PINA JUNIOR, JOSE COELHO DE - IME
- Unidade: IME
- Sigla do Departamento: MAP
- Assunto: MATEMÁTICA APLICADA
- Idioma: Português
- Resumo: Our objective in this work is to study the problem of converting a given matrix to an incidence matrix of a graph using elementary row operations and column-scaling, if such a conversion is possible. This problem is a particular case of the more abstract matroid graph realization (mgr) problem, which is: given a matroid m, decide whether m is isomorphic to a matroid of a graph and, if such is the case, construct such a graph. Tutte [1960] gave a polinomial algorithm to solve the mgr problem when m is binary, that is, given by a matrix over gf (2). Bixby & wagner [1988] designed a faster algorithm based on a particular graph decomposition. Bixby & cunningham [1980] showed how the mgr problem can be solved in polinomial-time when m is representable over a field, by reducing this problem to the binary case. Finally, seymour [1981] solved the mgr problem in the general case. These algorithms are related to the polinomial-time algorithm for testing whether a given matrix is totally unimodular, which is a consequence of seymour's famous decomposition theorem of regular matroids, in the sense that both rely on a reduction to the binary case. This work describes all the algorithms mentioned above, some in terms of matroids and others in terms of matrices and graphs
- Imprenta:
- Data da defesa: 11.09.1990
-
ABNT
PINA JÚNIOR, José Coelho de. Estrutura grafica de matrizes. 1990. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1990. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-113724/. Acesso em: 23 abr. 2024. -
APA
Pina Júnior, J. C. de. (1990). Estrutura grafica de matrizes (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-113724/ -
NLM
Pina Júnior JC de. Estrutura grafica de matrizes [Internet]. 1990 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-113724/ -
Vancouver
Pina Júnior JC de. Estrutura grafica de matrizes [Internet]. 1990 ;[citado 2024 abr. 23 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-113724/ - Length-bounded disjoint paths in planar graphs
- Lempel, Even, and Cederbaum planarity method
- Improved bound for the Caratheodory rank of the bases of a matroid
- Algorithms for terminal Steiner trees
- Multilength single pair shortest disjoint paths
- On the integer cone of the bases of a matroid
- A new bound for the Carathéodory rank of the bases of a matroid
- Algorithms for terminal Steiner trees
- Counting Hamiltonian cycles in the matroid basis graph
- Spanning trees with nonseparating paths
Como citar
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
