臺灣博碩士論文加值系統

本論文給出一演算法，使得當輸入有重量的有向圖G=(V,E)、點s∈V及一預測（且可能錯誤）的根於s之最短路徑樹T時，該演算法會在O(η|V||E|+|E|)時間內輸出所有點v∈V的最短s-v距離，其中η表示滿足d_G (s,v)≠d_T (s,v)的點v∈V所佔之比例。我們的演算法修改了貝爾曼－福特演算法

This thesis shows an algorithm that, given a weighted directed graph G=(V,E), a vertex s∈V and a predicted (and possibly wrong) shortest-path tree T rooted at s, outputs the shortest s-v distance for all v∈V in O(η|V||E|+|E|) time, where η denotes the fraction of vertices v∈V satisfying d_G (s,v)≠d_T (s,v). Our algorithm modifies the Bellman–Ford algorithm.

1. Introduction
2. Result
3. Conclusions
REFERENCES

[1]R. Bellman, “On a routing problem,” Q. Appl. Math., vol. 16, no. 1, pp. 87–90, 1958.
[2]L. R. Ford, Network Flow Theory. Santa Monica, CA: RAND Corporation, 1956.
[3]A. V. Goldberg and C. Harrelson, “Computing the shortest path: A* search meets graph theory.,” in SODA: Symposium on Discrete Algorithms, 2005, vol. 5, pp. 156–165.
[4]U. Meyer and P. Sanders, “Δ-stepping: a parallelizable shortest path algorithm,” J. Algorithms, vol. 49, no. 1, pp. 114–152, 2003.
[5]Z. Akata et al., “A research agenda for hybrid intelligence: augmenting human intellect with collaborative, adaptive, responsible, and explainable artificial intelligence,” Computer, vol. 53, no. 8, pp. 18–28, 2020.
[6]S. Raisch and S. Krakowski, “Artificial intelligence and management: The automation–augmentation paradox,” Acad. Manage. Rev., vol. 46, no. 1, pp. 192–210, 2021.
[7]T. Dao, A. Gu, A. Ratner, V. Smith, C. De Sa, and C. Ré, “A kernel theory of modern data augmentation,” in ICML: International Conference on Machine Learning, 2019, pp. 1528–1537.
[8]E. Du, F. Wang, and M. Mitzenmacher, “Putting the “Learning,” in ICML: International Conference on Machine Learning, 2021, pp. 2860–2869.
[9]C. L. Hedrick, “Routing information protocol,” RFC Editor, 1988.
[10]J. Kelly and M. Walker, “The Critical Path Method,” Remington Rand DuPont Corp., 1957.
[11]S. Khuller, B. Raghavachari, and N. Young, “Balancing minimum spanning trees and shortest-path trees,” Algorithmica, vol. 14, no. 4, pp. 305–321, 1995.