Abstract
The cutwidth problem is to find a linear layout of a network so that the maximal number of cuts (cw) of a line separating consecutive vertices is minimized. A related and more natural problem is the cyclic cutwidth (ccw) when a circular layout is considered. The main question is to compare both measures cw and ccw for specific networks, whether adding an edge to a path and forming a cycle reduces the cutwidth essentially. We prove exact values for the cyclic cutwidths of the 2-dimensional ordinary and cylindrical meshes P m ×P n and P m ×C n ; respectively. Especially, if m ≥ n + 3; then ccw(P m × P n ) = cw(P m × P n ) = n + 1 and if n is even then ccw(P n × P n ) = n-1 and cw(P n × P n ) = n + 1 and if m≥ 2; n ≥ 3; then ccw(P m × C n ) = minm + 1, n + 2:
Acknowledgment
The work of the second author was partly done while he was visiting LaBRI, Universitée Bordeaux I, team of Prof. A. Raspaud.
This research was supported by grant No. 95/5305/277 of Slovak Grant Agency and by grant of British Council to the Project Loughborough Reconfigurable Array and Theoretical Aspects of Interconnection Networks. The research of the last two authors was supported also by the grant of EU INCO-COP 96-0195.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alon, N., West, D. B., The Borsuk-Ulam theorem and bisection of necklaces, Proceedings of the American Mathematical Society 98 (1986), 623–628.
Bel Hala, A., Congestion optimale du plongement de l’ypercube H(n) dans la chaine P(2n), RAIRO Informatique, Théorique et Applications 27 (1993), 1–17.
Bermond, J.-C., Gargano, L., Perennes, S., Rescigno, A., Vaccaro, U., Efficient collective communication in optical networks, in: Proc. of ICALP’96, LNCS 1099, Springer Verlag, Berlin, 1996, 574–585.
Bezrukov, S. L., Edge isoperimetric problems on graphs, in: Proc. Bolyai Mathematical Studies, Budapest, 1998.
Bezrukov, S. L., Schroeder, U.-P., The cyclic wirelength of trees, Discrete Applied Mathematics 87 (1998), 275–277.
Chavez, J. D., Trapp, R., The cyclic cutwidth of trees, Discrete Applied Mathematics 87 (1998), 25–32.
Chung, F. R. K., Labelings of graphs, in: Selected Topics in Graph Theory 3, (L. Beineke and R. Wilson eds.), Academic Press, New York, 1988, 151-168.
Gavril, F., Some NP-complete problems on graphs, in: Proc. of the 11th Conf. on Information Sciences and Systems, Johns Hopkins University, Baltimore, MD, 1977, 91–95.
Goldberg, C. H., West, D. B., Bisection of circle colorings, SIAM J. Alg. Disc. Meth. 6 (1985), 93–106.
Hu, Q., Zhang, Y., Shen, X., Rearrangeable graphs, in: Proc. of COCOON’97, LNCS 1276, Springer Verlag, Berlin, 1997, 441–450.
Hromkovič, J., Müller, V., S´ykora, O., Vrt’o, I., On embeddings in cycles, Information and Computation 118 (1995), 302–305.
Lin, Y., S´ykora, O., Vrt’o, I., On cyclic cutwidths, submitted for publication, 1997.
Lopez, A. D., Law, H. F. S., A dense gate matrix layout method for MOS VLSI, IEEE Transactions on Electronic Devices 27, (1980), 1671–1675.
Paterson, M. S., Schröder, H., S´ykora, O., Vrt’o, I., On permutation communications in all-optical rings, in: Proc. of SIROCCO’98, University of Salerno, Amalfi, 1998, 1–7.
Rolim, J., S´ykora, O., Vrt’o, I., Optimal cutwidth of meshes, in: Proc. 21 th Intl. Workshop on Graph-Theoretic Concepts in Computer Science, LNCS 1017, Springer Verlag, Berlin, 1995, 252–264.
Schröder, H., S´ykora, O., Vrt’o, I., Optical all-to-all communication for some product graphs, in: Proc. of SOFSEM’97, LNCS 1338, Springer Verlag, Berlin, 1997, 555–562.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Schröder, H., Sýykoa, O., Vrt’o, I. (1999). Cyclic Cutwidth of the Mesh. In: Pavelka, J., Tel, G., Bartošek, M. (eds) SOFSEM’99: Theory and Practice of Informatics. SOFSEM 1999. Lecture Notes in Computer Science, vol 1725. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-47849-3_33
Download citation
DOI: https://doi.org/10.1007/3-540-47849-3_33
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66694-3
Online ISBN: 978-3-540-47849-2
eBook Packages: Springer Book Archive