臺灣博碩士論文加值系統

一個圖形的帶寬（bandwidth）是該圖形上相鄰頂點之間最大編號差的最小值。圖形帶寬的最小值問題有相當廣泛的應用範圍，例如在稀疏矩陣的儲存、平行計算網路、超大型積體電路的設計、及反向追蹤於強制滿足問題等等。若在將圖形中的邊給予編號，該圖之邊帶寬（edge-bandwidth）則定義為圖形上相鄰邊之間最大編號差的最小值。圖形之邊帶寬問題是包含於圖形之帶寬問題的一個子問題，求得一個邊圖形（line graph）的帶寬值就相當於求得一個或多個圖形的邊帶寬值。然而圖形之邊帶寬問題的計算複雜度至今仍不為人知。與帶寬相似的圈帶寬（cyclic bandwidth），亦可應用於平行計算網路及超大型積體電路的設計上。對任意圖形而言，求其帶寬或圈帶寬的最小值問題，都是NP-Complete的問題。本論文針對一些特定圖形給予其帶寬、邊帶寬、及圈帶寬問題的解。

The bandwidth of a graph is the minimum of the maximum difference between labels of adjacent vertices in the graph. Bandwidth of graphs is an useful parameter for many applications including solving linear equations, parallel computation network, VLSI layout problem, back tracing in the constraint satisfaction problem etc. If we label the edges instead of the vertices of the graph, we can define the edge-bandwidth accordingly. The edge-bandwidth of a graph is the minimum of the maximum difference between labels of adjacent edges in the graph. The edge-bandwidth problem is a restricted version of the bandwidth problem. Establishing the bandwidth of a line graph is equivalent to verifying the edge-bandwidth of one or more graphs. However, the computing complexity of the edge-bandwidth is unknown up to now. Another parameter which is related to bandwidth is called cyclic bandwidth of a graph. The application about the cyclic bandwidth is also in the area of parallel computation network and VLSI layout. It is known that the decision problems corresponding to finding the bandwidth and the cyclic bandwidth of an arbitrary graph are NP-complete. In this thesis we solved bandwidth, edge-bandwidth and cyclic bandwidth for some classes of graphs with extensive proof.

中文摘要 i
Abstract ii
List of Figures vi
List of Tables vii
CHAPTER 1 INTRODUCTION 1
1.1 Motivation and Background 1
1.2 Terminology 3
1.3 Organization 7
CHAPTER 2 APPLICATIONS AND SOME KNOWN RESULTS 9
2.1 Applications 9
2.2 Some Known Results 11
CHAPTER 3 BANDWIDTH OF SOME GRAPH PRODUCTS 18
3.1 Composition of a Complete Bipartite Graph with Other Graphs 18
3.2 Strong Product of a Complete Bipartite Graph with Other Graphs 22
3.3 Tensor Product of a Complete Graph with a Complete Graph 29
CHAPTER 4 SOME RESULTS OF EDGE-BANDWIDTH AND CYCLIC BANDWIDTH 32
4.1 Edge-Bandwidth for the Tensor Product of a Path with a Path 32
4.2 Edge-Bandwidth for the Tensor Product of a Path with a Cycle 35
4.3 Cyclic Bandwidth of a d-Dimensional Hypercube 41
CHAPTER 5 CONCLUSIONS AND FUTURE WORKS 43
5.1 Conclusions 43
5.2 Future Works 44
REFERENCES 46

[1] S. N. Bhatt and F. T. Leighton, 1984, “A framework for solving VLSI graph layout problems,” Journal of Computer and System Sciences, Vol. 28. no. 2, pp. 300-343.
[2] H. L. Bodlaender and J. van Leeuwen, 1986, “Simulation of large networks on smaller networks,” Information and Control, Vol. 71, pp. 143-180.
[3] G. Chartrand and L. Lesniak, 1996, “Graphs & digraphs,” Chapman & Hall/CRC.
[4] P. Z. Chinn, J. Chvátalová, A. K. Dewdney and N. E. Gibbs, 1982, “The bandwidth problem for graphs and matrices－a survey,” Journal of Graph Theory, Vol. 6, no. 3, pp. 233-254.
[5] P. Z. Chinn, Y. Lin, J. Yuan and K. Williams, 1995, “Bandwidth of the composition of certain graph powers,” Ars Combinatoria, Vol. 39, pp. 167-173..
[6] F. R. K. Chung, 1988, “Labelings of Graphs,” Selected Topics in Graphs Theory, Vol. 3, pp. 151-168.
[7] V. Chvátal, 1970, “A remark on a problem of Harary,” Czechoslovak Mathematical Journal, Vol. 20, pp. 109-111.
[8] J. Chvátalová, A.K. Dewdney, N. E. Gibbs and R. R. Korfhage, 1975, “The bandwidth problem for graphs: a collection of recent results,” Research Report #24, Department of Computer Science, UWO, London, Ontario.
[9] J. Chvátalová and J. Opatrny, 1986, “The bandwidth problem and operations on graphs,” Discrete Mathematics, Vol. 61, pp. 141-150.
[10] G. Confessore, P. Dell’Olmo and S. Giordani, 1998, “An approximation result for a bandwidth allocation problem,” Operations research proceedings, 1997 (Jena), Springer, Berlin, pp. 126-131.
[11] A. Dingle and I. H. Sudborough, 1989, “Simulation of binary trees and X-trees on pyramid networks,” Proceeding of the 1st Annual IEEE Symposium on Parallel and Distributed Processing, pp. 210-219.
[12] A. Dingle and I. H. Sudborough, 1989, “Efficient uses of pyramid networks,” Proceeding of the 1st Annual IEEE Symposium on Parallel and Distributed Processing, pp. 220-229.
[13] D. Eichhorn, D. Mubayi, K. O’Bryant and D. West, 2000, “The edge-bandwidth of theta graphs,” Journal of Graph Theory, Vol. 35, no. 2, pp. 89-98.
[14] J. A. Ellis, S. Chow and D. Manke, 2003, “Many to one embeddings from grids into cylinders, tori, and hypercubes,” SIAM Journal on Computing, Vol. 32, no. 2, pp. 386-407.
[15] J. P. Fishburn and R. A. Finkel, 1982, “Quotient networks,” IEEE TC, Vol. 31, pp. 288-295.
[16] M. R. Garey, R. L. Graham, D. S. Johnson and D. E. Knuth, 1978, “Complexity results for bandwidth minimization,” SIAM Journal on Applied Mathematics, pp. 477-495.
[17] M. R. Garey and D. S. Johnson, 1979, “Computers and intractability: A guide to the theory of NP-completeness”, Freeman, New York.
[18] M. R. Garey, D. S. Johnson and R. L. Stockmeyer, 1974, “Some simplified NP-complete problems,” Proceedings of the 6th ACM Symposium on Theory of Computing, pp. 47-63.
[19] A. Gupta, 2000, “Embedding tree metrics into low-dimensional Euclidean spaces,” Discrete & Computational Geometry. An International Journal of Mathematics and Computer Science, Vol. 24, no. 1, pp. 105-116.
[20] A. Gupta, 2001, “Improved bandwidth approximation for trees and chordal graphs,” Journal of Algorithms, Vol. 40, no. 1, pp. 24-36.
[21] J. Hao, 2001, “Cyclic bandwidth sum of graphs,” Applied Mathematics. A Journal of Chinese University Ser. B, Vol. 16, no. 2, pp. 115-121.
[22] L. H. Harper, 1964, “Optimal assignments of numbers to vertices,” Journal of the Society for Industrial and Applied Mathematics, Vol. 12, pp. 131-135.
[23] L. H. Harper, 1966, “Optimal numberings and isoperimetric problems on graphs,” Journal of Combinatorial Theory, Vol. 1, pp. 385-393.
[24] U. Hendrich and M. Stiebitz, 1992, “On the bandwidth of graph products,” Journal of Information Processing and Cybernetics, Vol. 28, pp. 113-125.
[25] J. Hromkovic, V. Muller, O. Sykora, and I. Vrto, 1992, “On embedding interconnection networks into rings of processors,” Lecture Notes in Computer Science, Vol. 605, Springer, Berlin, pp. 53-62.
[26] T. Jiang, D. Mubayi, A. Shastri and D. B. West, 1999, “Edge-bandwidth of graphs,” SIAM Journal on Discrete Mathematics, Vol. 12, no. 3, pp. 307-316.
[27] T. Kloks, D. Kratsch and H. Müller, 1999, “Approximating the bandwidth for asteroidal triple-free graphs,” Journal of Algorithms, Vol. 32, no. 1, pp. 41-57.
[28] D. Kratsch and L. Stewart, 2002, “Approximating bandwidth by mixing layouts of interval graphs,” SIAM Journal on Discrete Mathematics, Vol. 15, no. 4, pp. 435-449.
[29] Y. L. Lai, 1997, “Bandwidth, edgesum and profile of graphs,” Ph. D. Dissertation, Department of Computer Science, Western Michigan University.
[30] Y. L. Lai and F. H. Chiang, 2002, “Bandwidth of some graph products,” Proceedings of the 6th World Multi-Conference on Systemics, Cybernetics and Informatics, Vol. XVI, pp. 7-11.
[31] Y. L. Lai and K. Williams, 1995, “Bandwidth of the strong product of paths and cycles,” Congressus Numeratium, Vol. 109, pp. 123-128.
[32] Y. L. Lai and K. Williams, 1997, “On bandwidth for the tensor product of paths and cycles,” Discrete Applied Mathematics, Vol. 73, pp. 133-141.
[33] Y. L. Lai and K. Williams, 1999, “A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs,” Journal of Graph Theory, Vol. 31, no. 2, pp. 75-94.
[34] P. C. B. Lam, W. C. Shiu and W. H. Chan, 1997, “On bandwidth and cyclic bandwidth of graphs,” Ars Combinatoria, Vol. 47, pp. 147-152.
[35] P. C. B. Lam, W. C. Shiu and W. H. Chan, 2002, “Characterization of graphs with equal bandwidth and cyclic bandwidth,” Discrete Mathematics, Vol. 242, no. 1-3, pp. 283-289.
[36] P. C. B. Lam, W. C. Shiu, W. H. Chan and Y. Lin, 1997, “On the bandwidth of convex triangulation meshes,” Discrete Mathematics, Vol. 173, no. 1-3, pp. 285-289.
[37] Y. Lin, 1994, “The cyclic bandwidth problem,” Systems Science and Mathematical Sciences, Vol. 7, no. 3, pp. 282-288.
[38] Y. Lin, 1997, “Minimum bandwidth problem for embedding graphs in cycles,” Networks, Vol. 29, no. 3, pp. 135-140.
[39] J. Liu, 1992, “On bandwidth sum for the composition of paths and cycles,” Technology Reports/92-06, Department of Computer Sciences, Western Michigan University.
[40] J. Liu and K. Williams, 1995, “On bandwidth and edgesum for the composition of two graphs,” Discrete Mathematics, Vol. 143, pp. 159-166.
[41] F. Makedon and I. H. Sudborough, 1989, “On minimizing width in linear layouts,” Discrete Applied Mathematics, Vol. 23, pp. 243-265.
[42] C. Mead and L. Conway, 1980, “Introduction to VLSI systems,” Addison-Wesley, Reading, Mass..
[43] D. J. Miller, 1968, “The categorical product of graphs,” Canadian Journal of Mathematics, Vol. 20, pp. 1511-1521.
[44] B. Monien and H. Sudborough, 1990, “Embedding one interconnection network in another,” Computing, Vol. 7, pp. 257-282.
[45] C. H. Papadimitriou, 1976, “The NP-completeness of the bandwidth minimization problem,” Computing, Vol. 16, pp. 263-270.
[46] C. D. Thompson, 1979, “Area-time complexity for VLSI,” Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing, pp. 81-88.
[47] C. D. Thompson, 1980, “A complexity theory for VLSI,” Ph. D. thesis, Carnegie-Mellon University Pittsburgh.
[48] P. M. Weichsel, 1962, “The kronecker product of graphs,” Proceedings of the American Mathematical Society, Vol. 13, pp. 47-52.
[49] K. Williams, 1994, “On bandwidth and edgesum for the tensor product of paths with complete bipartite graphs,” Congressus Numerantium, Vol. 102, pp. 183-190.
[50] K. Williams, 1996, “On bandwidth for the tensor product of paths and cycles with complete graphs,” Bulletin of the Institute Combinatorics and its Applications, Vol. 16, pp. 41-48.
[51] J. Yan, 1997, “The bandwidth problem in cographs,” Tamsui Oxford Journal of Mathematical Sciences, Vol. 13, pp. 31-36.
[52] J. Yan, 1998, “Algorithm aspects of the bandwidth problem on -sparse graphs,” Tamsui Oxford Journal Mathematical Sciences, Vol. 14, pp. 11-18.
[53] J. Yuan, 1994, “Some results about the cyclic bandwidth of graphs,” Journal of Xinjiang University. Nature Science, Vol. 11, no. 2, pp. 16-18, 41.
[54] J. Yuan and Y. Lin, 1993, “The bandwidth of the union of two graphs,” Mathematica Applicata, Vol. 6, pp. 256-261 (in Chinese).
[55] J. Yuan and Y. Lin, 1998, “The bandwidth of the complement of a k-tree,” Applied Mathematics. A Journal of Chinese Universities. Ser. B, Vol. 13, no. 4, pp. 451-454.
[56] R. Zabih, 1990, “Some applications of graph bandwidth to constraint satisfaction problems,” AAAI-90: Proceedings of the Eighth National Conference Artificial Intelligence MIT, Cambridge, MA, pp. 46-51.
[57] S. Zhou, 1997, “Harper-type lower bounds for the cyclic bandwidth of graphs,” Journal of Huazhoug University of Science and Technology, Vol. 25, suppl. I, pp. 92-94.
[58] S. Zhou, 2000, “Bounding the bandwidth for graphs,” Theoretical Computer Science, Vol. 249, no. 2, pp. 357-368.
[59] S. Zhou and J. Yuan, 1998, “Harper-type lower bounds and the bandwidth of the compositions of graphs,” Discrete Mathematics, Vol. 181, no. 1-3, pp. 255-266.