# 臺灣博碩士論文加值系統

(44.220.247.152) 您好！臺灣時間：2024/09/10 23:36

:::

### 詳目顯示

:

• 被引用:0
• 點閱:3
• 評分:
• 下載:0
• 書目收藏:0
 本論文給出一演算法，使得當輸入有重量的有向圖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. Introduction2. Result3. ConclusionsREFERENCES
 [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.
 電子全文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 隨機解對於賦距空間中的1-中位數與最大完美 匹配問題 2 隨機圖上求距離總和 3 超度量空間中最遠對的格雷碼 4 著名的一中位數演算法對抗雜訊的韌性研究 5 傾斜二進制數的加法 6 調整對稱距離函數以滿足三角不等式

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室