(54.236.62.49) 您好!臺灣時間:2021/03/08 02:21
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:邱圭琳
研究生(外文):Guei-Lin Chiu
論文名稱:驗證在強弦圖上樞紐點的演算法
論文名稱(外文):A Certifying Algorithm for Finding Hinge Vertices of Strongly Chordal Graphs
指導教授:王有禮
學位類別:碩士
校院名稱:國立暨南國際大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2008
畢業學年度:96
語文別:中文
論文頁數:51
中文關鍵詞:樞紐點強弦圖驗證演算法演算法
相關次數:
  • 被引用被引用:0
  • 點閱點閱:155
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載: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.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔