在一致的環狀串列上具自我穩定能力之交換配對

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：5

、訪客IP：18.220.126.5

姓名

李傳傑(Chuan-Chieh Lee) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

在一致的環狀串列上具自我穩定能力之交換配對
(Self-Stabilizing Alternative Matching on uniform rings)

相關論文

★ 在雙向一致任意大小的環上之具自我穩定能力之相位同步	★ 低空間需求之分散式最佳同步交互器
★ 利用區塊人臉特徵為基礎之混合式人臉辨識系統	★ 無線射頻辨識系統反碰撞協定
★ 同儕網路虛擬環境之高效能安全設計	★ 無線感測網路指向天線定位機制
★ 新一代GPS導航系統	★ 支援學習探索發問式閱讀之電子書
★ 評估電子書的螢幕數量及視窗管理影響學生學習及理解之成效	★ 運用體感互動建立學習系統中肢體與情境經驗之學習成效分析
★ 讓思考看得見：基於案例式推理學習的心思記錄器	★ 朝向利他性的學習評量系統
★ 可編輯情境的學習舞台	★ 展現寫作思考流程的範文閱讀平台

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本篇論文中，我們設計了一個空間最佳化的演算法來解決雙向鏈結串列中交換配對的問題。每個結點只用了一個指標，在系統穏定之後，在環狀鏈結中會一直存在個配對，系統收斂所需的期望時間為O(n2)。

摘要(英)

In this paper, we design a space optimal self-stabilizing algorithm for alternative matching on synchronous bidirectional uniform rings of any size. Each node keeps a pointer. After the system stabilizes, there are always matching pairs on the ring. The expected time for convergence is O(n2)

關鍵字(中)

★ 最大配對
★ 自我穏定
★ 配對
★ 交換配對

關鍵字(英)

★ maximum matching
★ alternative matching
★ self-stabilizing
★ matching

論文目次

Abstract……………………………………………………1
1. Introduction……………………………………………….1
2. The Self-Stabilizing Alternative Matching algorithm......2
3. Correctness and Analysis………………………………....5
3.1 Correctness……………………………………………...5
3.2 Analysis……………………………………………….....9
4. Conclusion……………………………………………......11
References…………………………………………………...11

參考文獻

References
[1] E.W. Dijkstra, “Self-stabilizing systems in spite of distributed control”, Communications of the ACM 17, pp.643-644, 1974.
[2] Z. Galil, “Efficient algorithms for finding maximum matchings in graphs”, ACM Computing Surveys, 18, 1, 1986.
[3] S. Ghosh, A. Gupta, M. H. Karaata, and S. V. Pemmaraju, “A self-stabilizing algorithm for maximal matching on trees”, Technical Report TR-94-06, Department of Computer Science, The University of Iowa, Iowa City, 1994.
[4] A. Gibbons, “Algorithmic Graph Theory”, Cambridge University Press, Cambridge, 1985.
[5] Ralph P. Grimaldi “Discrete and Combinatorial Mathematics”, ADDISON-WESLEY, 1998.
[6] T. Herman, “Probabilistic Stabilization”, Information Processing Letters, 35:63-67,1990.
[7] S.T. Huang, “The fuzzy philosophers”, J. Rolim et al. (Eds): IPDPS 2000 Workshops, LNCS 1800, pp. 130-136, 2000, Springer-Verlag Berlin Heidelberg 2000.
[8] S. C. Hsu and S.T. Huang, “A self-stabilizing algorithm for maximal matching”, Information Processing Letters, pp. 77-81, 1992,.
[9] J. L. W. Kessels, “An exercise in proving self-stabilization with a variant function”, Information Processing Letters, v.29 n.1, p.39-42, 1988
[10] S. Micali and V. V. Vazirani, “An algorithm for finding maximum matchings in general graphs”, 21st IEEE Annual Symposium on Foundations of Computer Science, 1980.

指導教授

黃興燦(Shing-Tsaan Huang)

審核日期

2004-6-23

推文