A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto
Neste trabalho é apresentado um algoritmo simplex para rede de complexidade <em>O(nm)</em> que encontra uma árvore de caminhos mais curtos, de um nó para todos os outros nós em uma rede direcionada, de n nós e m arcos, ou encontra um ciclo negativo. O tempo de execução desse algoritmo, n...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Essentia Editora IFFluminense
2010-05-01
|
| Series: | Vértices |
| Subjects: | |
| Online Access: | http://essentiaeditora.iff.edu.br/index.php/vertices/article/view/135 |
| _version_ | 1818910873155010560 |
|---|---|
| author | Carlos Eduardo Varejão Marinho Antonio José dos Santos Neto |
| author_facet | Carlos Eduardo Varejão Marinho Antonio José dos Santos Neto |
| author_sort | Carlos Eduardo Varejão Marinho |
| collection | DOAJ |
| description | Neste trabalho é apresentado um algoritmo simplex para rede de complexidade <em>O(nm)</em> que encontra uma árvore de caminhos mais curtos, de um nó para todos os outros nós em uma rede direcionada, de n nós e m arcos, ou encontra um ciclo negativo. O tempo de execução desse algoritmo, no pior caso, é tão rápido quanto qualquer algoritmo polinomial que resolva este problema. |
| first_indexed | 2024-12-19T22:49:43Z |
| format | Article |
| id | doaj.art-bad3a3918d4749c0ba1166eeaac2290c |
| institution | Directory Open Access Journal |
| issn | 1415-2843 1809-2667 |
| language | English |
| last_indexed | 2024-12-19T22:49:43Z |
| publishDate | 2010-05-01 |
| publisher | Essentia Editora IFFluminense |
| record_format | Article |
| series | Vértices |
| spelling | doaj.art-bad3a3918d4749c0ba1166eeaac2290c2022-12-21T20:02:52ZengEssentia Editora IFFluminenseVértices1415-28431809-26672010-05-015212313810.5935/1809-2667.20030015125A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curtoCarlos Eduardo Varejão MarinhoAntonio José dos Santos NetoNeste trabalho é apresentado um algoritmo simplex para rede de complexidade <em>O(nm)</em> que encontra uma árvore de caminhos mais curtos, de um nó para todos os outros nós em uma rede direcionada, de n nós e m arcos, ou encontra um ciclo negativo. O tempo de execução desse algoritmo, no pior caso, é tão rápido quanto qualquer algoritmo polinomial que resolva este problema.http://essentiaeditora.iff.edu.br/index.php/vertices/article/view/135Algoritmo simplex para redes. Complexidade. Árvores de busca. |
| spellingShingle | Carlos Eduardo Varejão Marinho Antonio José dos Santos Neto A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto Vértices Algoritmo simplex para redes. Complexidade. Árvores de busca. |
| title | A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto |
| title_full | A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto |
| title_fullStr | A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto |
| title_full_unstemmed | A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto |
| title_short | A EFICIÊNCIA POLIONOMIAL DO SIMPLEX PARA REDES: Aplicação em um problema do caminho mais curto |
| title_sort | eficiencia polionomial do simplex para redes aplicacao em um problema do caminho mais curto |
| topic | Algoritmo simplex para redes. Complexidade. Árvores de busca. |
| url | http://essentiaeditora.iff.edu.br/index.php/vertices/article/view/135 |
| work_keys_str_mv | AT carloseduardovarejaomarinho aeficienciapolionomialdosimplexpararedesaplicacaoemumproblemadocaminhomaiscurto AT antoniojosedossantosneto aeficienciapolionomialdosimplexpararedesaplicacaoemumproblemadocaminhomaiscurto AT carloseduardovarejaomarinho eficienciapolionomialdosimplexpararedesaplicacaoemumproblemadocaminhomaiscurto AT antoniojosedossantosneto eficienciapolionomialdosimplexpararedesaplicacaoemumproblemadocaminhomaiscurto |