請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30139完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 顏嗣鈞(Hsu-Chun Yen) | |
| dc.contributor.author | Shu-Fen Lin | en |
| dc.contributor.author | 林淑棻 | zh_TW |
| dc.date.accessioned | 2021-06-13T01:38:54Z | - |
| dc.date.available | 2008-07-17 | |
| dc.date.copyright | 2007-07-17 | |
| dc.date.issued | 2007 | |
| dc.date.submitted | 2007-07-11 | |
| dc.identifier.citation | [1] M. R. Garey, D. S. Johnson and L. Stockmeyer, “Some simplified NP-complete graph problems,” Theor. Comput. Sci. 1(1976)237-267.
[2] T. N. Bui and C. Jones, “Finding Good Approximate Vertex and Edge Partitions is NP-Hard, ” Information Processing Letters, vik. 42, pp.153-159, 1992. [3] B. Kernighan and S. Lin, “An efficient Heuristic Procedure for Partitioning Graphs,” Bell Systems Technical J., vol 49, pp. 291-307, Feb. 1970. [4] S. Kirkpatrick, C.D. Gelatt Jr., and M.P. Vecchi, “Optimization by Simulated Annealing,” Science, vol. 220, no. 4598, pp. 671-680, May 1983. [5] T. N Bui and B. R Moon, “Genetic Algorithm and Graph Partitioning,” IEEE Trans. Computers, vol. 45, no.7, pp.841-855, July 1996. [6] D. S. Johnson, C. R. Aragon, L.A. McGeoch, and C. Schevon, “Optimization by Simulated Anneling: An Experimental Evaluation; Part I, Graph Partitioning,” Operations Research, vol. 37, pp. 865-892, 1989. [7] R. Battiti, and A. A. Bertossi “Greedy, Prohibition, and Reactive Heuristics for Graph Partitioning”, IEEE Transactions on Computers, vol. 48, no.4 Apr. 1999. [8] T. N. Bui and C. Jones, “A Heuristic for Reducing Fill in Sparse Matrix Factorization,” Proc. Sixth SIAM Conf. Parallel Processing for Scientific Computing, pp. 445-452, 1993. [9] B. Hendrickson and R. Leland, “A multilevel Algorithm for Partitioning Graphs,” Technical Report SAND93-1301, SANDIA Nat’l Laboratory, 1993. [10] S. T. Barnard and H. D. Simon, “Fast Multilevel Implementation of Recursive Spectral Bisection for Partitioning Unstructured Problems,” Concurrency: Practice and Experience vol. 6, no. 2, pp. 101-117 1994. [11] F. Harary, Graph Theory (Addison-Wesley, Reading, MA, 1969) [12] R. Becker and Y. Perl, “The Shifting Algorithm Technique for the Partitioning of Trees,” Discrete Appl. Math., 62:15–34, 1995. [13] M. Lucertini, Y. Perl and B. Simeone, “Most Uniform Path Partitioning and Its Use in Image Processing,” Discrete Appl. Math. 42:227-256, 1993. [14] R. Becker, S.R. Schach and Y. Perl, “A Shifting Algorithm for Min-max Tree Partitioning,” J. ACM, 29:58–67, 1982. [15] R. I. Becker, Y. Perl and S. Schach, “An Efficient Algorithm for Min-max Tree Partition,” Quaestiones Inform. 2 (1982) 27-30. [16] P. Eades. “A Heuristic for Graph Drawing.” Congr. Numer., 42:149–160, 1984. [17] G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. “Graph Drawing: Algorithms for the Visualization of Graphs.” Prentice-Hall, Englewood Cliffs, NJ, 1998. [18] http://staffweb.cms.gre.ac.uk/~c.walshaw/partition/#SoperJoGO04 | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/30139 | - |
| dc.description.abstract | 在資訊科學研究中，圖形切割問題廣泛出現在多種領域內，其中也包括圖形繪製。在圖形繪製中，一個好的呈現在於是否將各節點間的相互關係表現出來。而區分的方式便是利用圖形切割演算法。
在本篇論文中，我們提出一個與過去不同的切割方法，先在樹上做切割，再對應到圖形上，藉以區分不同群集，進行一連串調整的動作找出最佳解，而最後利用force-directed placement的方法將圖形繪製出來。 過去在找尋k-partition的方法，最典型的是將原圖切割成兩份，再將其中一份切成兩份，以此類推，最後再稍作調整，而在本篇論文中，我們亦提出了一個方法，直接將原圖切成k份，但仍保留過去的方法以提供選擇。我們也分析何時採用何種方法較好，利用test graph 來測試兩者間的差異。 此篇論文最主要的貢獻在於：第一、提出與過去不同的方式來解決圖形切割的問題，第二、可利用此演算法來找出大概的群集數，第三、利用force-directed placement繪製圖形時，若將原圖分群可加速圖形達到穩定狀態。 | zh_TW |
| dc.description.abstract | The graph partitioning problem arises in many areas of computer science, including the application to graph drawing. In graph drawing, a good layout explicitly shows the relationship between all nodes. We present a graph partitioning algorithm based on tree partitioning to clearly separate one cluster from another, make some adjustments on clusters and find the best partition. Finally, we use force-directed placement algorithm to demonstrate the result in a visual form. The traditional solution to k-way partition is to find bisection recursively and generalize it into k partitions. We demonstrate another algorithm to divide the graph into k parts directly with some adjustments. These two ways for the k-way partition problems are compared empirically later.
Our contributions lie in providing a graph partitioning algorithm from different perspectives with lower complexity than before. In addition, we can find the number of clusters approximately using the algorithm presented in this thesis. While applied in graph drawing, this algorithm could reduce the number of steps in a force-directed placement algorithm. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-13T01:38:54Z (GMT). No. of bitstreams: 1 ntu-96-R94921090-1.pdf: 893801 bytes, checksum: 0e4f002dd318db1cee3925219d472e6f (MD5) Previous issue date: 2007 | en |
| dc.description.tableofcontents | Acknowledgement…………………………………………………………………… i
Abstract (Chinese) …………………………………………………………….. ……ii Abstract (English) ……………………………………………………………... ……iii Contents……………………………………………………………………………… iv List of Figures………………………………………………………………….. ……vi List of Tables………………………………………………………………………… viii Chapter 1 Introduction …………………………………………………………1 Chapter 2 Preliminaries …………………………………………………………5 2.1 Tree Partition with Shifting Techniques ………………………………5 2.2 Famous Approaches for Graph Partitioning …………………………8 2.2.1 Kernighan-Lin Graph Bisection Algorithm ……………………… 8 2.2.2 Simulated Annealing ………………………………………………10 2.2.3 Genetic Algorithm ………………………………………………10 Chapter 3 Algorithms for Most Uniform Tree Partitioning Problem …………11 3.1 Exhaustive Procedure ……………………………………………………12 3.2 UTP_R ……………………………………………………………………13 3.3 UTP_H ……………………………………………………………………15 Chapter 4 Unbalanced Graph Partitioning ……………………………………19 4.1 Initial Graph Partitioning ………………………………………………19 4.2 Local Improvement ……………………………………………………21 4.2.1 An Example …………………………………………………………22 4.2.2 Algorithm of Adjustments …………………………………………26 4.2.3 Algorithm of Graph Partitioning ………………………………32 Chapter 5 Application in Graph Drawing ……………………………………36 Chapter 6 Conclusions and Future Works ……………………………………46 References …………………………………………………………………………49 | |
| dc.language.iso | en | |
| dc.subject | 移動演算法 | zh_TW |
| dc.subject | 樹切割 | zh_TW |
| dc.subject | 圖形繪製 | zh_TW |
| dc.subject | 多層次非均衡圖形切割 | zh_TW |
| dc.subject | graph drawing | en |
| dc.subject | shifting algorithm | en |
| dc.subject | tree partitioning | en |
| dc.subject | multilevel unbalanced graph partitioning | en |
| dc.title | 多層次非均等圖形切割及在圖形繪製上的應用 | zh_TW |
| dc.title | Multilevel Unbalanced Graph Partitioning with Applications to Graph Drawing | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 95-2 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 雷欽隆,郭斯彥,黃秋煌,莊仁輝 | |
| dc.subject.keyword | 多層次非均衡圖形切割,樹切割,移動演算法,圖形繪製, | zh_TW |
| dc.subject.keyword | multilevel unbalanced graph partitioning,tree partitioning,shifting algorithm,graph drawing, | en |
| dc.relation.page | 59 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2007-07-13 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 電機工程學研究所 | zh_TW |
| 顯示於系所單位： | 電機工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-96-1.pdf 未授權公開取用 | 872.85 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。