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

(44.200.175.255) 您好！臺灣時間：2022/08/12 22:20

:::

### 詳目顯示

:

• 被引用:0
• 點閱:177
• 評分:
• 下載:12
• 書目收藏:0
 令G = (V, E)且令G−u 是被點集合V(G)−{u}所導出的子圖。在G中的點u∈V(G)被稱為樞紐點，若且唯若會存在兩點x, y∈V(G − u)，使得dG−u(x, y) > dG(x, y)。dG(x, y)表示x 和y 之間在G 裡的距離(最短路徑的長度)。ㄧ個問題的驗證演算法，指的是針對每個產生出的答案提供ㄧ個憑證。憑證是證據的一部份，證明答案不會在執行中受到錯誤的影響。在這篇論文中，我們提出一個Ο(n + m)時間的演算法，驗證在強弦圖上的樞紐點。
 ﻿　　Let G = (V, E) be a graph, and let G−u be the subgraph of G induced by the vertex set V(G) − {u}. A vertex u ∈ V(G) is said to be a hinge vertex of G if and only if there exist two vertices x, y ∈ V(G − u) such that dG−u(x, y) > dG(x, y), where dG(x , y) is the distance (i.e., the length of a shortest path) between x and y in G. A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence proving that the answer has not been compromised by a bug in the implementation. In this paper, we present an Ο(n + m) time certifying algorithm for finding all hinge vertices of strongly chordal graphs.
 1　緒言2　找尋Hinge Vertices的相關論文及作法 2.1　定義及特性 2.2　在Strongly Chordal Graphs上找Hinge Vertices 2.3　Chordal Graphs的介紹 2.4　Strongly Chordal Graphs的介紹 2.5　找到最大相鄰的點 2.5.1　找出所有的Hinge Vertices 2.5.2　演算法B的細節解說及範例 2.5.3　演算法B正確性的分析 2.6　使用演算法C在Strongly Chordal Graphs上找出所有的Hinge Vertices 2.6.1　演算法C的細節解說及範例 2.6.2　演算法C正確性的分析 2.7　其他相關研究3　我們的Certifying Algorithm 3.1　找出所有比自己大且相鄰的點 3.2　演算法D的細節解說及範例 3.3　我們的方法 3.4　演算法E的細節解說及範例 3.5　演算法E的正確性4　結論及未來研究方向 4.1　結論 4.2　未來研究的方向參考文獻
 [1] R. P. Anstee and M. Farber, Characterizations of totally balanced matrices, J. Algorithms, 5:215-230, 1984.[2] D. Bera, M. Pal, and T. K. Pal. An efficient algorithm for finding all hinge vertices on trapezoid graphs, Theory of Computing Systems, 36:17–27, 2003.[3] D. Bera, M. Pal and T. K. Pal, An optimal sequential and parallel algorithms to compute all hinge vertices on interval graphs, Korean Journal of Computational and Applied Mathematics, 8:387401, 2001.[4] J. M. Chang and C. W. Ho. The recognition of geodetically connected graphs, Information Processing Letters, 65:81–88, 1998.[5] J. M. Chang, C. W. Ho, C. C. Hsu and Y.L. Wang, The characterizations of hinge-free networks, in: Proc. Intemat.Computer Symp. on Algorithms, Taiwan, 105-112, 1996.[6] J. M. Chang, C. C. Hsu, Y. L. Wang and T. Y. Ho. Finding the set of all hinge vertices for strongly chordal graphs in linear time, Information Sciences, 99:173–182, 1997.[7] M. S. Chang, A certifying algorithm for the path cover problem on interval graphs, Proceedings of the 25th Workshop on Combinatorial Mathematics and Computation Theory, Taiwan, 25:255262, 2008.[8] G. A. Dirac, On rigid circuit graphs, Abhandlungen aus dem Mathematischen Seminar der Uniυersität Hamburg, 25:71-76, 1961.[9] M. Faber, Characterizations of strongly chordal graphs, Discrete Math., 43:173-189, 1983.[10] A. M. Farley and A. Proskurowski, Self-repairing networks, Parallel Processing Letters, 3 (4):381-391, 1993.[11] D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacific J. Math., 15:835-855, 1965.[12] E. Gavril, Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1:180187, 1972.[13] P. C. Gilmore and A.J. Hoffman, A characterization of comparability graphs and of interval graphs, Canad. J. Math.,16: 539-548, 1964.[14] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.[15] P. Hell and J. Huang, Certifying LexBFS recognition algorithms for proper interval graphs and proper interval bigraphs, SIAM J. Discrete Math., 18:554-570, 2004.[16] T.Y. Ho, Y. L. Wang and M. T. Juan, A linear time algorithm for finding all hinge vertices of a permutation graph, Information Processing Letters, 59:103–107, 1996.[17] H. Honma and S. Masuyama, A Parallel Algorithm for Finding All Hinge Vertices of an Interval Graph, IEICE TRANSACTIONS on Information and Systems, 84:419423, 2001.[18] H. Honma and S. Masuyama, A Parallel Algorithm for Finding All Hinge Vertices of a Trapezoid Graph, IEICE transactions on fundamentals of electronics, communications and computer sciences, 05:1031-1040, 2002.[19] H. Honma and S. Masuyama, An Optimal Parallel Algorithm for Finding All Hinge Vertices of a Circular-Arc Graph, IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 91:383391, 2008.[20] E. Howorka, A characterization of ptolemaic graphs, J. Graph Theory, 5:323331, 1981.[21] H. Kaplan and Y. Nussbaum, Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs, Lecture Notes in Comput. Sci., 4271:11-16, 2006.[22] D. Kratsch, R. M. McConnell, K. Mehlhorn, and Jeremy P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, SIAM J. Comput., 36:326-353, 2006.[23] D. Kratsch, R. M. McConnell, K. Mehlhorn, and J. P. Spinrad, Certifying algorithms for recognizing interval graphs and permutation graphs, SODA, 03:158-167, 2003.[24] D. Nikolopoulos and L. Palios, An O(nm)-Time Certifying Algorithm for Recognizing HHD-Free Graphs, Lecture Notes in Computer Sci., 4613:281-392, 2007.[25] R. Paige and R. E. Tarjan, Three partition refinement algorithms, SIAM J. Comput., 16:973-989, 1987.[26] A. Pnueli, A. Lempel and S. Even, Transitive orientation of graphs and identification of permutation graphs, Canada J. Math., 23:160-175, 1971.[27] D. J. Rose, Triangulated graphs and the elimination process, J. Math. Anal. Appl., 32:597-609, 1970.[28] D. J. Rose, A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations, in: R.C Read (Ed.), Graph theory and Computing, Academic Press, New York, 1972.[29] D. J. Rose, R.E. Tarjan and G.S. Lueker, Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5:266-283, 1976.[30] R. E. Tarjan, M. Yanakakis, Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13:566-579, 1984.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 圖形測度性質之研究：樞紐點與冪次圖

 無相關期刊

 1 第二短路徑問題之研究 2 在蜂巢圖上解決電力控制問題的演算法 3 二元樹間的4邊界旋轉距離 4 河內圖之最小邊排列編號 5 (n,k)-星形圖壞邊容錯之弱泛迴圈性質 6 應用於拍賣網頁分類目錄下的影像搜尋系統 7 基於搜尋引擎技術之影像搜尋系統 8 結合微機電系統感測器與視覺感測器追蹤三維人體姿態 9 應用特徵擷取、SVM和LSA於分析大量稀疏資料的推薦系統 10 考量視覺編排設計概念之自動化超媒體圖文合成系統 11 以情境與繪畫風格為導向之影像特效合成系統 12 以階層架構為基礎多層次的動態文字特效合成系統 13 以幾何圖形及色相為基礎之情境圖像版面佈置系統 14 以CIDOCCRM為基礎之文物知識漸進式推論系統 15 具錯誤更正能力之二元算數碼其植基於格狀圖之循序式最大事後機率解碼技巧之研究

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