Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional (1994)
- Authors:
- Autor USP: HASHIMOTO, RONALDO FUMIO - IME
- Unidade: IME
- Sigla do Departamento: MAC
- Subjects: ALGORITMOS E ESTRUTURAS DE DADOS; COMPUTABILIDADE E COMPLEXIDADE
- Language: Português
- Abstract: Neste trabalho estudamos varios problemas sobre circuitos e caminhos em grafos e em digrafos. Consideramos aqui tres classes de problemas: de existencia, de busca e de busca de um minimo. Para cada uma dessas classes investigamos os casos em que o objeto em questao e um circuito par/impar ou um caminho par/impar. Discutimos questoes referentes a complexidade computacional desses problemas e apresentamos algoritmos polinomiais para resolver varios deles. A maioria dos resultados que apresentamos foram coletados da literatura, incluindo uma resenha atualizada sobre o problema da existencia de circuitos pares em digrafos (um problema cuja complexidade computacional continua desconhecida ha vinte anos). Nossa principal contribuicao a este estudo e o desenvolvimento de um algoritmo linear para encontrar circuitos impares em digrafos. Descrevemos tambem algoritmos alternativos (nao necessariamente de melhor complexidade) para alguns dos problemas
- Imprenta:
- Data da defesa: 25.04.1994
-
ABNT
HASHIMOTO, Ronaldo Fumio. Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional. 1994. Dissertação (Mestrado) – Universidade de São Paulo, São Paulo, 1994. Disponível em: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005043/. Acesso em: 29 mar. 2024. -
APA
Hashimoto, R. F. (1994). Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional (Dissertação (Mestrado). Universidade de São Paulo, São Paulo. Recuperado de https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005043/ -
NLM
Hashimoto RF. Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional [Internet]. 1994 ;[citado 2024 mar. 29 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005043/ -
Vancouver
Hashimoto RF. Circuitos e caminhos pares/impares em grafos e digrafos - algoritmo e complexidade computacional [Internet]. 1994 ;[citado 2024 mar. 29 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005043/ - An extension of an algorithm for finding sequential decomposition of erosions and dilations
- Incremental and efficient computation of families of component trees
- Biological sequence analysis using complex networks and entropy maximization: a case study in SARS-CoV-2
- Evaluation of the impact of initial positions obtained by clustering algorithms on the straight line segments classifier
- Is cross-validation better than resubstitution for ranking genes?
- Growing genetic regulatory networks from seed genes
- Inference of restricted stochastic Boolean GRN' s by Bayesian error and entropy based criteria
- A new training algorithm for pattern recognition technique based on straight line segments
- A Monte Carlo approach to measure the robustness of Boolean networks
- Growing seed genes from time series data and thresholded Boolean networks with perturbation
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas