請用此 Handle URI 來引用此文件：
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65623完整後設資料紀錄
| DC 欄位 | 值 | 語言 |
|---|---|---|
| dc.contributor.advisor | 趙坤茂(Kun-Mao Chao) | |
| dc.contributor.author | An-Chiang Chu | en |
| dc.contributor.author | 朱安強 | zh_TW |
| dc.date.accessioned | 2021-06-16T23:54:33Z | - |
| dc.date.available | 2017-07-27 | |
| dc.date.copyright | 2012-07-27 | |
| dc.date.issued | 2012 | |
| dc.date.submitted | 2012-07-18 | |
| dc.identifier.citation | [1] K. Andreev and H. Ra ̈cke, Balanced graph partitioning, In Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2004), pp. 120–124, 2004.
[2] K. Andreev and H. R ̈acke, Balanced graph partitioning, Theory of Computing Systems, Vol. 39, Number 6, pp. 929–939, 2006. [3] E. Agasi, R. I. Becker and Y. Perl, A shifting algorithm for constrained min-max par- tition on trees, Discrete Applied Mathematics, Vol. 45, Number 1, pp. 1–28, 1993. [4] R. I. Becker and Y. Perl, Shifting algorithms for tree partitioning with general weighting functions, Journal of Algorithms, Vol. 4, Number 2, pp. 101–120, 1983. [5] R. I. Becker and Y. Perl, The shifting algorithm technique for the partitioning of trees, Discrete Applied Mathematics, Vol. 62, Number 1-3, pp. 15–34, 1995. [6] R. I. Becker, S. R. Schach and Y. Perl, A shifting algorithm for min-max tree parti- tioning, Journal of the Association for Computing Machinery, Vol. 29, Number 1, pp. 58–67, 1982. [7] R. I. Becker, B. Simeone and Y. Chiang, A shifting algorithm for continuous tree par- titioning, Theoretical Computer Science, Vol. 282, Number 2, pp. 353–380, 2002. [8] R. Benkoczi, B. Bhattacharya and Q. Shi, New upper bounds on continuous tree edge- partition problem, In Proceedings of the Fourth International Conference on Algorithmic Aspects in Information and Management (AAIM 2008), Lecture Notes in Computer Science, Vol. 5034, pp. 38–49, 2008. [9] R. Bordawekar, O. Shmueli, An algorithm for partitioning trees augmented with sibling edges, Information Process Letters, Vol. 108, Number 3, pp.136–142, 2008. [10] R. B. Boppana, Eigenvalues and graph bisection: an average-case analysis, In Pro- ceedings of the Twenty-eighth Annual Symposium on Foundations of Computer Science (FOCS 1987), pp. 280–285, 1987. [11] H. Broersma, D. Kratsch and G. J. Woeginger, Fully Decomposable Split Graphs, In Proceeding of the Twentieth International Workshop (IWOCA 2009), Lecture Notes in Computer Science, Vol. 5874, pp. 105–112, 2009. [12] T. N. Bui, A note on an improved bisection algorithm, Information Processing Letters, Vol. 10, Number 1, pp. 35–36, 1980. [13] T. N. Bui, C. Heigham, C. Jones and T. Leighton, Improving the performance of the Kernighan-Lin and simulated annealing graph bisection algorithms, In proceedings of the Twenty-sixth ACM/IEEE Design Automation Conference (DAC 1989), pp. 775-778, 1989. [14] T. N. Bui, S. Chaudhuri, F. T. Leighton, M. Sipser, Graph Bisection Algorithms with Good Average Case Behavior, In proceedings of the twenty-fifth Annual Symposium on Foundations of Computer Science, (FOCS 1984), pp. 181–192, 1984. [15] T. Bui, S. Chaudhuri, T. Leighton and M. Sipser, Graph bisection algorithm with good average case behavior, Combinatorica, Vol. 7, Number 22, pp. 171–191, 1987. [16] J. Chleb ́ıkov ́a, Approximating the maximally balanced connected partition problem in graphs, Information Processing Letters, Vol. 60, Number 5, pp. 225–230, 1996. [17] A.-C. Chu, B. Y. Wu, H.-L. Wang and K.-M. Chao, A tight bound of the min-ratio edge-partition problem on a tree, Discrete Applied Mathematics, Vol 158, Number 14, pp. 1471–1478, 2010. [18] A.-C. Chu, B. Y. Wu and K.-M. Chao, A linear-time algorithm for finding an edge- partition with max-min ratio at most two, Discrete Applied Mathematics, accepted with minor revision. [19] T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, Third Edition, The MIT Press, Massachusetts, 2009. [20] S. Dye, A note on the minimum bounded edge-partition of a tree, Discrete Applied Mathematics, Vol .157, Number 13, pp. 2958–2963, 2009. [21] M. E. Dyer and A. M. Frieze, On the complexity of partitioning graphs into connected subgraphs, Discrete Applied Mathematics, Vol. 10, Number 2, pp. 139–153, 1985. [22] G. Fan, B. Xu, X. Yu and C. Zhou, Upper bounds on minimum balanced bipartitions, Discrete Mathematics, Vol. 312, Number 6, pp. 1077–1083, 2012. [23] G. N. Frederickson, Optimal algorithms for tree partitioning, In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1991), pp. 168– 177, 1991. [24] G. N. Frederickson, Optimal parametric search algorithms in trees I: tree partition- ing, Technical Report, Computer Science Department, Purdue University, CS-TR-1029, 1992. [25] G. N. Frederickson and D. B. Johnson, Finding kth paths and p-centers by generating and searching good data structures, Journal of Algorithms, Vol. 4, Number 1, pp. 61–80, 1983. [26] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman and Company, San Francisco, 1979. [27] M. C. Golumbic, Algorithmic graph theory and perfect graphs, Academic Press, New York, 1980. [28] N. Halman and A. Tamir, Continuous bottleneck tree partitioning problems, Discrete Applied Mathematics, Vol. 140, Number 1-3, pp. 185–206, 2004. [29] T. Ito, K. Goto, X. Zhou and T. Nishizeki, Partitioning a multi-weighted graph to con- nected subgraphs of almost uniform size, In Proceedings of the Twelfth Annual Inter- national Conference (COCOON 2006), Lecture Notes in Computer Science, Vol. 4112, pp. 63–72, 2006. [30] T. Ito, K. Goto, X. Zhou and T. Nishizeki, Partitioning a multi-weighted graph to connected subgraphs of almost uniform size, IEICE Transactions, Vol. 90-D, Number 1, pp. 449–456, 2007. [31] T. Ito, T. Nishizeki, M. Schro ̈der, T. Uno and X. Zhou, Partitioning a weighted tree into subtrees with weights in a given range, Algorithmica, Vol. 62, Number 3-4, pp. 823–841, 2012. [32] T. Ito, T. Uno, X. Zhou and T. Nishizeki, Partitioning a weighted tree to subtrees of almost uniform size, In Proceedings of the Nineteenth International Symposium on Algorithms and Computation (ISAAC 2008), Lecture Notes in Computer Science, Vol. 5369, pp. 196–207, 2008. [33] T. Ito, X. Zhou and T. Nishizeki, Partitioning a weighted graph to connected subgraphs of almost uniform size, In Proceedings of the Thirtieth International Workshop (WG 2004), Lecture Notes in Computer Science, Vol. 3353, pp. 365–376, 2004. [34] T. Ito, X. Zhou and T. Nishizeki, Partitioning a graph of bounded tree-width to con- nected subgraphs of almost uniform size, Journal of Discrete Algorithms, Vol. 4, Number 1, pp. 142–154, 2006. [35] J. A. Lukes, Efficient algorithm for the partitioning of trees, IBM Journal of Research and Development, Vol. 18, Number 3, pp. 217–224, 1974. [36] B. W. Kernighan, Optimal sequential partitions of graphs, Journal of the Association for Computing Machinery, Vol. 18, Number 1, pp. 34–40, 1971. [37] S. Kundu and J. Misra, A linear tree partitioning algorithm, SIAM Journal on Com- puting, Vol. 6, Number 1, pp 151–154, 1977. [38] C.-C. Kanne and G. Moerkotte, A linear time algorithm for optimal tree sibling par- titioning and approximation algorithms in natix, In Proceedings of the Thirty-second International Conference on Very Large Data Bases (VLDB 2006), pp. 91–102, 2006. [39] J.-J. Lin, C.-Y. Chan and B.-F. Wang, Improved algorithms for the continuous tree edge-partition problems and a note on ratio and sorted matrices searches, Discrete Applied Mathematics, Vol. 158, Number 8, pp. 932–942, 2010. [40] M. Lucertini, Y. Perl and B. Simeone, Most uniform path partitioning and its use in image processing, Discrete Applied Mathematics, Vol. 42, Number 2, pp. 227–256, 1993. [41] N. Megiddo, Applying parallel computation algorithms in the design of serial algorithms, Journal of the Association for Computing Machinery, Vol. 30, Number 4, pp 852–865, 1983. [42] Y. Perl and S. R. Schach, Max-min tree partitioning, Journal of the Association for Computing Machinery, Vol. 28, Number 1, pp. 5–15, 1981. [43] Y. Perl and Uzi Vishkin Efficient implementation of a shifting algorithm, Discrete Ap- plied Mathematics, Vol 12, Number 1, pp. 71–80, 1985. [44] M. Schro ̈der, Balanced tree partitioning, Ph.D. Thesis, University of Karlsruhe, Ger- many, 2001. [45] Y. G. Saab and V. B. Rao, Fast effective heuristics for the graph bisectioning prob- lem, IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 9, Number 1, pp. 91–98, 1990. [46] Y. G. Saab, A fast and robust network bisection algorithm, IEEE Transactions on Computers, Vol. 44, Number 7, pp. 903–913, 1995. [47] K. Takamizawa, T. Nishizeki and N. Saito, Linear-time computability of combinatorial problems on series-parallel graphs, Journal of the Association for Computing Machinery, Vol.29, Number 3, pp. 623–641, 1982. [48] B. Y. Wu and K.-M. Chao, Spanning Trees and Optimization Problems, Chapman and Hall/CRC Press, Boca Raton, Florida, 2004. [49] B. Y. Wu, H.-L. Wang, S.-T. Kuan and K.-M. Chao, On the uniform edge-partition of a tree, Discrete Applied Mathematics, Vol. 155, Number 10, pp. 1213–1223, 2007. [50] B. Xu, J. Yan and X. Yu, A note on balanced bipartitions, Discrete Mathematics, Vol. 310, Number 20, pp. 2613–2617, 2010. [51] B. Xu, J. Yan and X. Yu, Balanced judicious bipartitions of graphs, Journal of Graph Theory, Vol. 63, Number 3, pp. 210–215, 2010. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/65623 | - |
| dc.description.abstract | 當給定正整數 k 以及對於一個邊數為 n 的無向連通圖，我們關心的是把此圖的邊分割成 k 個連通子圖，使得每一部份的大小盡可能地均勻。在此篇論文以最大塊與最小塊的邊數比來當作衡量的標準。在此課題上，過去的文獻只探討當圖限制為樹的結構，且邊為無權重之情況。對於 k=2,3 及 4 的情況，已被證明最大塊與最小塊的邊數比可以保證在 2 以內。而對於任意的 k ，先前最佳的結果是保證最大塊與最小塊的邊數比在 3 以內。
此篇論文將圖推廣至一個邊有權重的任意連通圖。當每個邊的權重不超過平均權重的一半時，我們提出一個線性時間的演算法來得到此圖的邊切割，使得最大塊與最小塊的邊數比可以保持在 2 以內。此外，我們也藉由一個例證來說明邊權重的限制是最寬鬆的。 | zh_TW |
| dc.description.abstract | Given a positive integer k and an undirected edge-weighted connected simple graph G with n edges, where k ≤ n, we wish to partition the graph into k edge-disjoint connected components of approximately the same size. We focus on the max-min ratio of the partition, which is the weight of the maximum component divided by that of the minimum component. For k = 2,3, and 4, it has been shown that the upper bound of the max-min ratio of an unweighted tree is two. For any k, the best previous upper bound of the max-min ratio of an unweighted tree is three.
In this thesis, for any graph with no edge of weight larger than one half of the average weight of a component, we provide a linear-time algorithm for delivering a partition with max-min ratio at most two. Together with the fact that the max-min ratio is at least two for some instances, we have that the max-min ratio upper bound attained in this thesis is tight. Furthermore, by an extreme example, we show that the above restriction on edge-weights is the loosest possible. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-16T23:54:33Z (GMT). No. of bitstreams: 1 ntu-101-D96922003-1.pdf: 647640 bytes, checksum: 2e7cd3a8045c6e78261f6561603f750a (MD5) Previous issue date: 2012 | en |
| dc.description.tableofcontents | Acknowledge i
Abstract in Chinese iii Abstract v Table of Contents viii List of Figures x List of Algorithms xi Terminology and Notation xiii 1 Introduction 1 1.1 ProblemDefinition ................................ 2 1.2 The Complexity of Partitioning Graphs into Connected Subgraph . . . . . . 3 1.3 Main Results ................................... 5 1.4 Organization of the Thesis............................ 6 1.5 Related Work................................... 8 2 Preliminaries 15 2.1 Terminology.................................... 15 2.2 Splitting Lemma ................................. 16 2.3 Previous Results on Connected-Edge-Partition ................................. 17 2.4 A Connected-Edge-Partition with Max-min Ratio at Most Four ............. 19 3 An O(n2)-Time Algorithm for Connected-Edge-Partition of a Tree 23 3.1 Edge-Partition Paths............................... 23 3.2 The Evolution Process ............................ 24 3.3 The Evaluation Function........................... 26 3.4 Time Analysis................................... 29 4 An O(n + k3)-Time Algorithm for Connected-Edge-Partition of a Tree 33 4.1 Algorithm VWBT ................................ 33 4.2 Algorithm Shift ................................. 36 4.3 Time Analysis................................... 38 4.4 Algorithm CompressTree ........................... 39 5 An O(n)-Time Algorithm for Connected-Edge-Partition of a Graph 45 5.1 Maximal λ-packing ................................ 46 5.2 Algorithm Mix .................................. 50 5.3 Algorithm VBalance .............................. 57 5.4 Connected-Edge-Partitionof a Tree....................... 60 5.5 Connected-Edge-Partitionof a Graph...................... 61 5.6 TheRestrictiononEdge-Weights ........................ 63 6 Concluding Remarks 65 6.1 Other Objectives on the Connected-Edge-Partition of a Graph ............. 66 6.2 No Restriction on Edge-Weights......................... 66 6.3 Exact Algorithms for Optimal Max-Min Ratio .................... 67 Bibliography 69 | |
| dc.language.iso | en | |
| dc.subject | 邊切割 | zh_TW |
| dc.subject | 點切割 | zh_TW |
| dc.subject | 圖切割 | zh_TW |
| dc.subject | 樹 | zh_TW |
| dc.subject | 演算法 | zh_TW |
| dc.subject | 圖論 | zh_TW |
| dc.subject | graph partition | en |
| dc.subject | graph theory | en |
| dc.subject | algorithm | en |
| dc.subject | edge-partition | en |
| dc.subject | vertex-partition | en |
| dc.subject | tree | en |
| dc.title | 圖的均勻邊切割問題 | zh_TW |
| dc.title | Uniform Edge-Partition of a Graph | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 100-2 | |
| dc.description.degree | 博士 | |
| dc.contributor.oralexamcommittee | 陳健輝(Gen-Huey Chen),傅楸善(Chiou-Shann Fuh),呂育道(Yuh-Dauh Lyuu),劉邦鋒(Pangfeng Liu),吳邦一(BangYi Wu) | |
| dc.subject.keyword | 邊切割,點切割,圖切割,樹,演算法,圖論, | zh_TW |
| dc.subject.keyword | edge-partition,vertex-partition,graph partition,tree,algorithm,graph theory, | en |
| dc.relation.page | 75 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2012-07-19 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| 顯示於系所單位： | 資訊工程學系 | |
文件中的檔案：
| 檔案 | 大小 | 格式 | |
|---|---|---|---|
| ntu-101-1.pdf 未授權公開取用 | 632.46 kB | Adobe PDF |
系統中的文件，除了特別指名其著作權條款之外，均受到著作權保護，並且保留所有的權利。