(3.238.36.32) 您好!臺灣時間:2021/02/27 09:44
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:葉錦誠
研究生(外文):Jin-Cheng Ye
論文名稱:以 Bisimplicial 特性來定義圖形類別的研究
論文名稱(外文):A Study of Graph Classes by Bisimplicial Property
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-Lung Peng
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:103
論文頁數:27
中文關鍵詞:單純點序列一般圖
外文關鍵詞:cliquebisimplicialgeneral graphcograph
相關次數:
  • 被引用被引用:0
  • 點閱點閱:50
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:5
  • 收藏至我的研究室書目清單書目收藏:0
在一個圖形中,若一個點v的鄰居所形成的誘導子圖是一個完全子圖的話,則v被稱作Simplicial。如果點v的鄰居所形成的誘導子圖是兩個完全子圖的聯集,則v被稱作Bisimplicial。在本論文中,我們研究一些具有Bisimplicial點性質的圖形。根據這個性質,我們可以為這些圖形建造出一個Bisimplicial序列。在此論文中,我們提出了一個O(n^4)的演算法在一般圖上判斷該圖是否存在一個Bisimplicial序列,同時我們也提出一個O(n^2)的演算法來判斷一個補圖是否具有這個序列。
A vertex v is called simplicial (respectively, bisimplicial) if the subgraph induced by N(v) is a clique (respectively, the union of two cliques). We investigate the class of graphs defined by the property that every induced subgraph has a vertex which is bisimplicial. By using this property, we propose algorithms for constructing bisimplicial elimination ordering on general graphs and cographs in O(n^4) and O(n^2) respectively.
Abstract i
Contents ii
List of Figures iii
1 Introduction 1
2 Algorithm for General Graphs 5
3 Algorithm for Cographs 15
4 Conclusion and Future Work 23
Bibliography 25
[1] L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, P. Seymour, Bisimplicial vertices in even-hole-free graphs. Journal of Combinatorial Theory, Series B, pp.1119–1146, 2000.
[2] A. Berry, R. Pogorelcnik, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Information Processing Letters, Vol.111, pp. 508–501, 2011.
[3] T. Biedl, Graph-theoretic algorithms, Lecture notes of a graduate course on university of Waterloo, 2005.
[4] J.R.S. Blair, B.W Peyton, An introduction to chordal graphs and clique trees, Engineering Physics and Mathematics Division, 1992.
[5] A. Brandstdt, V.B. Le, J.P. Spinrad, Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.
[6] A.E. Brouwer, W.H. Haemers, Spectra of graphs, Springer, 2011.
[7] F. Cazalsa, C. Karandeb, A note on the problem of reporting maximal cliques, Theoretical Computer Science, Vol. 407, pp. 564–568, 2008.
[8] D.G. Corneil, Lexicographic breadth first search A survey, Graph-Theoretic Concepts in Computer Science, pp. 1–19, 2005.
[9] M. De, S.C. Nandyb, S. Royc, In-place algorithms for computing a largest clique in geometric intersection graphs, Discrete Applied Mathematics 2014.
[10] D. Eppstein, The Traveling Salesman Problem for Cubic Graphs, Journal of Graph Algorithms and Applications, Vol. 11, pp. 61-81, 2007.
[11] M. Habib, V. Limouzy, On some simplicial elimination schemes for chordal graphs, Electronic otes in Discrete Mathematics, Vol. 32, pp. 125–132, 2009.
[12] M. Habiba, R. McConnell, C. Paul, L. Viennot, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theoretical Computer Science, Vol. 234, pp. 59–84, 2000.
[13] M. Habib, C. Paul, A simple linear time algorithm for cograph recognition, Discrete Applied Mathematics, Vol 145, pp. 183–197, 2005
[14] C.T Hong, S. Hougardy, F. Maffray, N.V.R Mahadev, On simplicial and cosimplicial vertices in graphs, Discrete Applied Mathematics, Vol. 138, pp. 117-132, 2004.
[15] H.A Jung, On a Class of Posets and the corresponding comparability graphs, Journal OF Combinatorial Theory B, Vol. 24, pp. 125–133, 1978.
[16] H. Lerchs, On cliques and kernels structure of graphs, Department of Computer Science, 1972.
[17] D.J. Rose, Triangulated graphs and the elimination process, Journal of Mathematical Analysis And Application, Vol. 32, pp. 597–609, 1970.
[18] D.J. Rose, R. E.TarJan, Algoritimic aspects of vertex elimination, Proceedings of seventh annual ACM symposium on Theory of computing, pp. 245–254,1975.
[18] D.J. Rose, R. E.TarJan, Algoritimic aspects of vertex elimination, Proceedings of seventh annual ACM symposium on Theory of computing, pp. 245–254,1975.
[20] K. Vuskovic, Even-hole-free graphs: A Survey, Applicable Analysis and Discrete Mathematics, pp. 219–240, 2010.



連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔