O problema do 1-centro em árvores: variações e aplicações

Nascimento, Isis Paulo do

Please use this identifier to cite or link to this item: https://rima.ufrrj.br/jspui/handle/20.500.14407/20012

Full metadata record

DC Field	Value	Language
dc.contributor.author	Nascimento, Isis Paulo do	-
dc.date.accessioned	2025-02-07T15:05:04Z	-
dc.date.available	2025-02-07T15:05:04Z	-
dc.date.issued	2023-08-30	-
dc.identifier.citation	NASCIMENTO, Isis Paulo do. O problema do 1-centro em árvores: variações e aplicações. 2023. 44f. Dissertação (Mestrado em Modelagem Matemática e Computacional) - Instituto de Ciências Exatas, Universidade Federal Rural do Rio de Janeiro, Seropédica, 2023.	pt_BR
dc.identifier.uri	https://rima.ufrrj.br/jspui/handle/20.500.14407/20012	-
dc.description.abstract	Problemas de localização possuem aplicações em diversas áreas, incluindo o estudo do plane- jamento de redes de distribuição de energia. No presente trabalho, apresentamos o problema do 1-centro modificado em árvores com aplicações ao estudo do redimensionamento de redes de energia, bem como um algoritmo para a resolução do problema em tempo O(n), onde conside- ramos pesos e distâncias positivas. A pesquisa também inclui a apresentação de resultados computacionais para alguns dos méto- dos apresentados, como os métodos de resolução em tempo O(n 2 ), O(n log n) e O(n), assim como novas estratégias para a aplicação de problemas de localização ao projeto de redes de distribuição de energia.	pt_BR
dc.description.sponsorship	Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES	pt_BR
dc.language	por	pt_BR
dc.publisher	Universidade Federal Rural do Rio de Janeiro	pt_BR
dc.subject	Árvores	pt_BR
dc.subject	problemas de localização	pt_BR
dc.subject	1-centro	pt_BR
dc.subject	Trees	pt_BR
dc.subject	location problems	pt_BR
dc.subject	1-center	pt_BR
dc.title	O problema do 1-centro em árvores: variações e aplicações	pt_BR
dc.title.alternative	The problem of 1-center in trees: variations and applications	en
dc.type	Dissertação	pt_BR
dc.description.abstractOther	Location problems have applications in many areas, including the study of the planning of power distribution systems. In the present work, we present the modified 1-center problem in trees, with applications to the study of resizing of power distribution networks, as well as an algorithm to solve the problem in O(n) time, considering positive weights and distances. The research also includes the presentation of computational results for some of the methods presented, such as the resolution methods in O(n 2 ), O(n log n) and O(n) time, and new strate- gies for the application of location problems to the design of power distribution networks.	en
dc.contributor.advisor1	Vera-Tudela, Carlos Andrés Reyna	-
dc.contributor.advisor1ID	https://orcid.org/0000-0001-5855-8611	pt_BR
dc.contributor.advisor1Lattes	http://lattes.cnpq.br/6509989261742578	pt_BR
dc.contributor.advisor-co1	Queiroz, Aquiles Braga de	-
dc.contributor.advisor-co1Lattes	http://lattes.cnpq.br/4356065339264046	pt_BR
dc.contributor.referee1	Vera-Tudela, Carlos Andrés Reyna	-
dc.contributor.referee1ID	https://orcid.org/0000-0001-5855-8611	pt_BR
dc.contributor.referee1Lattes	http://lattes.cnpq.br/6509989261742578	pt_BR
dc.contributor.referee2	Cruz, Marcelo Dib	-
dc.contributor.referee2ID	https://orcid.org/0000-0002-0380-144X	pt_BR
dc.contributor.referee2Lattes	http://lattes.cnpq.br/7385995443437070	pt_BR
dc.contributor.referee3	Silva, Robson Mariano da	-
dc.contributor.referee3Lattes	http://lattes.cnpq.br/9019994973988827	pt_BR
dc.contributor.referee4	Pinto, Paulo Eustáquio Duarte	-
dc.contributor.referee4ID	https://orcid.org/0000-0002-7393-3464	pt_BR
dc.contributor.referee4Lattes	http://lattes.cnpq.br/5413422509570085	pt_BR
dc.creator.Lattes	http://lattes.cnpq.br/0898208755952644	pt_BR
dc.publisher.country	Brasil	pt_BR
dc.publisher.department	Instituto de Ciências Exatas	pt_BR
dc.publisher.initials	UFRRJ	pt_BR
dc.publisher.program	Programa de Pós-Graduação em Modelagem Matemática e Computacional	pt_BR
dc.relation.references	AHO, A.; HOPCROFT, J.; ULLMAN, J. The Design and Analysis of Computer Algorithms. [S.l.]: Addison-Wesley — Reading, MA, 1974. ANEEL. Agência Nacional de Energia Elétrica – Regulação dos Serviços de Distribuição. 2022. Disponível em: <https://antigo.aneel.gov.br/web/guest/ regulacao-dos-servicos-de-distribuicao>. ASSIS, L. de; FRANCA, P.; USBERTI, F. A redistricting problem applied to meter reading in power distribution networks. Comput. Oper. Res., Elsevier Science Ltd., GBR, v. 41, p. 65–75, jan 2014. ISSN 0305-0548. Disponível em: <https://doi.org/10.1016/j.cor.2013.08.002>. BANIK, A. et al. The $p$-center problem in tree networks revisited. CoRR, abs/1604.07535, 2016. Disponível em: <http://arxiv.org/abs/1604.07535>. BEN-MOSHE, B. et al. Efficient algorithms for center problems in cactus networks. The- oretical Computer Science, v. 378, n. 3, p. 237–252, 2007. ISSN 0304-3975. Algo- rithms and Computation. Disponível em: <https://www.sciencedirect.com/science/article/pii/ S0304397507001247>. BHATTACHARYA, B.; DAS, S.; DEV, S. R. The Weighted k-Center Problem in Trees for Fixed k. In: LU, P.; ZHANG, G. (Ed.). 30th International Symposium on Algorithms and Com- putation (ISAAC 2019). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informa- tik, 2019. (Leibniz International Proceedings in Informatics (LIPIcs), v. 149), p. 27:1–27:11. ISBN 978-3-95977-130-6. ISSN 1868-8969. Disponível em: <https://drops.dagstuhl.de/opus/ volltexte/2019/11523>. BHATTACHARYA, B. et al. Optimal algorithms for the path/tree-shaped facility location problems in trees. In: Proceedings of the 17th International Conference on Algorithms and Computation. Berlin, Heidelberg: Springer-Verlag, 2006. (ISAAC’06), p. 379–388. ISBN 3540496947. Disponível em: <https://doi.org/10.1007/11940128_39>. BHATTACHARYA, B.; SHI, Q. Improved algorithms to network p-center location problems. Computational Geometry, v. 47, n. 2, Part C, p. 307–315, 2014. ISSN 0925-7721. The 20th Canadian Conference on Computational Geometry(CCCG 2008). Disponível em: <https: //www.sciencedirect.com/science/article/pii/S0925772113000278>. BHATTACHARYA, B. K. et al. Constant work-space algorithms for facility location problems. Discrete Applied Mathematics, v. 283, p. 456–472, 2020. ISSN 0166-218X. Disponível em: <https://www.sciencedirect.com/science/article/pii/S0166218X20300573>. BURKARD, R.; KRARUP, J. A linear algorithm for the pos/neg-weighted 1-median problem on a cactus. Computing, v. 60, p. 193–215, 1998. CABELLO, S.; ROTE, G. Obnoxious centers in graphs. SIAM Journal on Discrete Mathema- tics, v. 24, n. 4, p. 1713–1730, 2010. Disponível em: <https://doi.org/10.1137/09077638X>. CALIK, H.; LABBÉ, M.; YAMAN, H. p-center problems, g. laporte, s. nickel, f. saldanha da gama (eds.). In: SPRINGER (Ed.). Location Science. [S.l.]: Springer International Publishing Switzerland, 2015. CAMICIA, R.; VICENTE, A. Grafos e madiana. In: Anais da XXII Semana Acadêmica de Matemática da Unioeste. Cascavel, PR - Brasil: [s.n.], 2008. COGIS, O.; ROBERT, C. Théorie des Graphes: Au-delà des Ponts de Königsberg, Problèmes, Théorèmes, Algorithmes. [S.l.]: Vuibert, 2003. CORMEN, T. H. et al. Introduction to Algorithms, Third Edition. 3rd. ed. [S.l.]: The MIT Press, 2009. ISBN 0262033844. DASKIN, M.; MAASS, K. The p-median problem. In: LAPORTE, G.; NICKEL, S.; GAMA, F. S. da (Ed.). Location Science. Switzerland: Springer International Publishing, 2015. GARCIA, V. et al. Grasp para o problema de planejamento de redes ssecundárias de distribuição de energia elétrica. In: Anais do XXXV SBPO. Natal, RN - Brasil: [s.n.], 2003. p. 1427–1437. GAREY, M.; JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP- Completeness. [S.l.]: W. H. Freeman, 1979. ISBN 0-7167-1044-7. GOLDMAN, A. Optimal center location in simple networks. Transportations Sci., v. 2, p. 77– 91, 1962. GOLDMAN, A. Optimal center location in simple networks. Transportations Sci., v. 5, p. 212– 221, 1971. GØRTZ, I. L.; WIRTH, A. Asymmetry in k-center variants. Theoret. Comput. Sci, v. 361, p. 188–199, 2006. HAKIMI, S. Optimum distribution of switching centers in a communication network and some related graph theoretic problems. Operations Research, v. 13, p. 462–475, 1965. HAKIMI, S.; SCHMEICHEL, E.; PIERCE, J. On p-centers in networks. Transportation Sci., v. 12, p. 1–15, 1978. HANDLER, G.; MIRCHANDANI, P. Location on Networks: Theory and Algorithms. [S.l.]: The MIT Press, 1979. HARARY, F. Graph Theory. [S.l.]: Addison-Wesley — Reading, MA, 1969. HARTMANN, T. A.; LENDL, S.; WOEGINGER, G. J. Continuous facility location on graphs. In: BIENSTOCK, D.; ZAMBELLI, G. (Ed.). Integer Programming and Combinatorial Opti- mization. [S.l.]: Springer, 2020. p. 171–181. 42 HUA, L. Applications of mathematical models to wheat harvesting (english translation in chin. math. 2 (1962), 77-91). Acta Mathematica Sinica, v. 11, p. 63–75, 1961. JAEGER, M.; GOLDBERG, J. A polynomial algorithm for the equal capacity p-center problem on trees. Transportation Sci., v. 28, p. 167–175, 1994. KARIV, O.; HAKIMI, S. An algorithmic approach to network location problems. part 1: The p-centers. SIAM J. Appl. Math., v. 37, p. 513–538, 1979. KARIV, O.; HAKIMI, S. An algorithmic approach to network location problems. part 2: The p-medians. SIAM J. Appl. Math., v. 37, p. 539–560, 1979. LIU, Y. An optimization-driven dynamic vehicle routing algorithm for on-demand meal delivery using drones. Computers & Operations Research, v. 111, p. 1–20, 2019. MEGIDDO, N. Linear-time algorithms for linear programming in r3 and related problems. SIAM J. Comput., v. 12, p. 759–776, 1983. NASCIMENTO, I. Algoritmos de Particionamento e de Localização em Árvores — Monogra- fia de Graduação. Bacharelado em Matemática Aplicada e Computacional. Dissertação (B.S. Thesis) — Instituto Multidisciplinar - Universidade Federal Rural do Rio de Janeiro, 2018. NGUYEN, K.; ANH, L. Inverse k-centrum problem on trees with variable vertex weights. Mathematical Methods of Operational Research, v. 82, 05 2015. NGUYEN, K.; NGUYEN-THU, H.; HUNG, N. Combinatorial algorithms for the uniform-cost inverse 1-center problem on weighted trees. Acta Mathematica Vietnamica, v. 44, 08 2018. PLESNíK, J. A heuristic for the p-center problems in graphs. Discrete Applied Mathematics, v. 17, n. 3, p. 263–268, 1987. ISSN 0166-218X. Disponível em: <https://www.sciencedirect. com/science/article/pii/0166218X87900291>. PUERTO, J.; RODRíGUEZ-CHíA, A.; TAMIR, A. On the planar piecewise quadratic 1-center problem. Algorithmica (New York), v. 57, p. 252–283, 02 2010. RABUSKE, M. A. Introdução à Teoria dos Grafos. [S.l.]: Editora da UFSC, 1992. SILVA, M.; FRANCA, P.; SILVEIRA, P. Long-range planning of power distribution systems: Secondary networks. Computers & Electrical Engineering, v. 22, p. 179–191, 1996. TAMIR, A. An o(pn2 ) algorithm for the p-median and related problems on tree graphs. Oper. Res. Lett., v. 19, p. 59–64, 1996. TANSEL, B.; FRANCIS, R.; LOWE, T. Location on networks: A survey. part i: The p-center and p-median problems. Management Science, v. 29, p. 482–497, 1983. TANSEL, B.; FRANCIS, R.; LOWE, T. Location on networks: A survey. part ii: Exploiting tree network structure. Management Science, v. 29, p. 498–511, 1983. WANG, H.; ZHANG, J. Computing the center of uncertain points on tree networks. Algorith- mica, v. 78, 05 2016. WANG, H.; ZHANG, J. An o(n\log n)-time algorithm for the k-center problem in trees. CoRR, abs/1705.02752, 2017. Disponível em: <http://arxiv.org/abs/1705.02752>. YE, J.-H.; LI, C.-Y.; WANG, B.-F. An improved algorithm for the minmax regret path centdian problem on trees. Journal of Computer and System Sciences, v. 97, 06 2018. 43 YU, H.; LI, C.; LEE, D. T. The multi-service center problem. Theor. Comput. Sci., v. 705, p. 58–74, 2018. Disponível em: <https://doi.org/10.1016/j.tcs.2017.09.034>. YU, H.; LIN, T.; WANG, B. Improved algorithms for the minmax-regret 1-center and 1-median problems. ACM Trans. Algorithms, v. 4, n. 3, p. 36:1–36:27, 2008. Disponível em: <https: //doi.org/10.1145/1367064.1367076>.	pt_BR
dc.subject.cnpq	Ciência da Computação	pt_BR
Appears in Collections:	Mestrado em Modelagem Matemática e Computacional

Se for cadastrado no RIMA, poderá receber informações por email.
Se ainda não tem uma conta, cadastre-se aqui!

Files in This Item:

File	Description	Size	Format
2023 - Isis Paulo do Nascimento.pdf		1.26 MB	Adobe PDF	View/Open

Show simple item record