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: 02 mar. 2026. -
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 2026 mar. 02 ] 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 2026 mar. 02 ] Available from: https://teses.usp.br/teses/disponiveis/45/45132/tde-20210729-005043/ - Pattern recognition based on straight line segments
- Growing seed genes from time series data and thresholded Boolean networks with perturbation
- Segmentation of retinal blood vessels based on ultimate elongation opening
- A Monte Carlo approach to measure the robustness of Boolean networks
- A new training algorithm for pattern recognition technique based on straight line segments
- An approach to growth delimitation of straight line segment classifiers based on a minimum bounding box
- Is cross-validation better than resubstitution for ranking genes?
- Inference of restricted stochastic Boolean GRN' s by Bayesian error and entropy based criteria
- Growing genetic regulatory networks from seed genes
- Efficient incremental computation of attributes based on locally countable patterns in component trees
How to cite
A citação é gerada automaticamente e pode não estar totalmente de acordo com as normas
