Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45015Full metadata record
| ???org.dspace.app.webui.jsptag.ItemTag.dcfield??? | Value | Language |
|---|---|---|
| dc.contributor.advisor | 陳文進 | |
| dc.contributor.author | Chen-Chu Su | en |
| dc.contributor.author | 蘇承祖 | zh_TW |
| dc.date.accessioned | 2021-06-15T04:01:24Z | - |
| dc.date.available | 2010-03-10 | |
| dc.date.copyright | 2010-03-10 | |
| dc.date.issued | 2010 | |
| dc.date.submitted | 2010-02-22 | |
| dc.identifier.citation | [1] Daniel J. Kleitman. The crossing number of K5,n. J. Combinatorial Theory, 9:315–
323, 1970. [2] M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312–316, 1983. [3] Ken-ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. In STOC’07—Proceedings of the 39th Annual ACM Symposium on Theory of Computing, pages 382–390. ACM, 2007. [4] Shengjun Pan and R. Bruce Richter. The crossing number of K11 is 100. J. Graph Theory, 56(2):128–134, 2007. [5] D. R. Woodall. Cyclic-order graphs and Zarankiewicz’s crossing-number conjecture. J. Graph Theory, 17(6):657–671, 1993. [6] Alice M. Dean and R. Bruce Richter. The crossing number of C4 × C4. J. Graph Theory, 19(1):125–129, 1995. [7] Jay Adamsson and R. Bruce Richter. Arrangements, circular arrangements and the crossing number of C7 × Cn. J. Combin. Theory Ser. B, 90(1):21–39, 2004. [8] Yuanqiu Huang and Tinglei Zhao. The crossing number of K1,4,n. Discrete Math., 308(9):1634–1638, 2008. [9] Kouhei Asano. The crossing number of K1,3,n andK2,3,n. J. Graph Theory, 10(1):1– 8, 1986. [10] Yuanqiu Huang and Mei Hanfei. The crossing number of K1,5,n. International J.Math. Combin., 1(1):33–44, 2007. [11] Yuan Qiu Huang and Ting Lei Zhao. On the crossing number of the complete tripartite K1,6,n. Acta Math. Appl. Sin., 29(6):1046–1053, 2006. [12] Yuanqiu Huang and Tinglei Zhao. On the crossing number of the complete tripartite graph K1,8,n. Acta Math. Sci. Ser. A Chin. Ed., 26(7):1115–1122, 2006. [13] Jing Wang and Yuan Qiu Huang. Crossing number of the complete tripartite graph K1,10,n. Appl. Math. J. Chinese Univ. Ser. A, 23(3):349–356, 2008. [14] Pak Tung Ho. The crossing number of K1,m,n. Discrete Math., 308(24):5996–6002, 2008. | |
| dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/45015 | - |
| dc.description.abstract | 交叉數是一個圖，在平面上所有的畫法中，可以畫出最小的交叉數。在這篇論
文，根據Kleitman證明完全二分圖的結果，我們證明了對於所有的n， K2,4,n這個 完全三分圖的交叉數。最後，我們提出了關於K2,m,n交叉數的猜想。 | zh_TW |
| dc.description.abstract | The crossing Number $cr(G)$ of a graph $G$ is the smallest crossing number among all drawings of $G$ in the plane.
In this paper, we determine the crossing number of the tripartite graph $K_{2,4,n}$ for any integer $n$. Our proof depends on Kleitman's results for the complete bipartite graphs. At last, we propose a conjecture of the crossing number of $K_{2,m,n}$. | en |
| dc.description.provenance | Made available in DSpace on 2021-06-15T04:01:24Z (GMT). No. of bitstreams: 1 ntu-99-R96922077-1.pdf: 256195 bytes, checksum: c335352ca7d4c2a50893b733ecdcc4d5 (MD5) Previous issue date: 2010 | en |
| dc.description.tableofcontents | Acknowledgement i
Chinese Abstract ii Abstract iii List of Figures v 1 Introduction 1 2 Notation 3 3 Proof of The Crossing Number of K2,4,n 3.1 Some Lemmas . . . . . . . . . . . . 4 3.2 The Crossing Number of K2,4,n . . . 6 4 Conclusion 13 References 14 | |
| dc.language.iso | en | |
| dc.subject | 圖 | zh_TW |
| dc.subject | 交叉數 | zh_TW |
| dc.subject | 完全二分圖 | zh_TW |
| dc.subject | 完全三分圖 | zh_TW |
| dc.subject | NP完備 | zh_TW |
| dc.subject | complete tripartite graph | en |
| dc.subject | Crossing number | en |
| dc.subject | NP-complete | en |
| dc.subject | graph | en |
| dc.subject | complete bipartite graph | en |
| dc.title | K2,4,n之交叉數 | zh_TW |
| dc.title | The Crossing Number of K2,4,n | en |
| dc.type | Thesis | |
| dc.date.schoolyear | 98-1 | |
| dc.description.degree | 碩士 | |
| dc.contributor.oralexamcommittee | 陳俊良,呂學一 | |
| dc.subject.keyword | 交叉數,圖,完全二分圖,完全三分圖,NP完備, | zh_TW |
| dc.subject.keyword | Crossing number,graph,complete bipartite graph,complete tripartite graph,NP-complete, | en |
| dc.relation.page | 15 | |
| dc.rights.note | 有償授權 | |
| dc.date.accepted | 2010-02-22 | |
| dc.contributor.author-college | 電機資訊學院 | zh_TW |
| dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
| Appears in Collections: | 資訊工程學系 | |
Files in This Item:
| File | Size | Format | |
|---|---|---|---|
| ntu-99-1.pdf Restricted Access | 250.19 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.