Tese

Estrutura grafica de matrizes (1990)

• Authors:
  • Pina Júnior, José Coelho de
  • Mandel, Arnaldo (Orientador)
• Autor USP: PINA JUNIOR, JOSE COELHO DE - IME
• Unidade: IME
• Sigla do Departamento: MAP
• DOI: 10.11606/D.45.1990.tde-20220712-113724
• Assunto: MATEMÁTICA APLICADA
• Language: Português
• Abstract: 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:
  • Publisher place: São Paulo
  • Date published: 1990
• Data da defesa: 11.09.1990


Informações sobre a disponibilidade de versões do artigo em acesso aberto coletadas automaticamente via oaDOI API (Unpaywall).

Status:

Artigo possui versão em acesso aberto em repositório (Green Open Access)

Versão do Documento:

Versão submetida (Pré-print)

Acessar versão aberta:

• URL de acesso aberto
• PDF de acesso aberto

Por se tratar de integração com serviço externo, podem existir diferentes versões do trabalho (como preprints ou postprints), que podem diferir da versão publicada.

---

How to cite

A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas

• 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: 10 abr. 2026.

• 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 2026 abr. 10 ] 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 2026 abr. 10 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20220712-113724/

Últimas obras dos mesmos autores vinculados com a USP cadastradas na BDPI:

• Length-bounded disjoint paths in planar graphs
• Improved bound for the Caratheodory rank of the bases of a matroid
• Algorithms for terminal Steiner trees
• Algorithms for terminal Steiner trees
• On the integer cone of the bases of a matroid
• hashify: uma ferramenta para visualização de hashes com animações
• Lempel, Even, and Cederbaum planarity method
• A new bound for the Carathéodory rank of the bases of a matroid
• Counting Hamiltonian cycles in the matroid basis graph
• Spanning trees with nonseparating paths