Abstract
A (linear) layout of an undirected graph G is a one-to-one function mapping the vertices of G to integers. The cutwidth of G under a linear layout L, denoted by cw(G,L), is the maximum, taken over all possible i, of the number of edges connecting vertices assigned to integers less than i to vertices assigned to integers at least as large as i. The cutwidth of a graph G, denoted by cw(G), is the minimum of cw(G,L), taken over all possible linear layouts L. The problem of determining the cutwidth of a graph, called the Min Cut Linear Arrangement problem, has applications in VLSI, for example in the minimization of interconnection channels in Weinberger arrays [16].
We describe a relationship between the cutwidth of a graph G and its “search number” [10], denoted by s(G). We show that, for all graphs G, s(G) ≤ cw(G) ≤ ≫deg(G)/ 2⌋ · s(G), where deg(G) denotes the maximum degree of any vertex in G. In particular, this means that, for any graph G with maximum vertex degree 3, s(G)=cw(G).
The earlier dynamic programming algorithm of Gurari and Sudborough [5 ] is improved to show that, for any k≥2, the problem of deciding if a given graph has cutwidth at most k can be done in O(nk−1) steps. We also characterize the classes of graphs with cutwidth 2 and cutwidth 3. The latter characterization strongly suggests a linear time algorithm to determine whether a given graph has cutwidth at most three.
A portion of this work was completed while at the National Technical University of Athens, in Athens, Greece
supported in part by NSF Grant number MCS 81-09280
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
References
M. A. Breuer, “Min Cut Placement”, J. Design Automation and Fault Tolerant Computing 1,4 ( 1977 ), pp. 343–362.
M.-J. Chung, F. S. Makedon, I. H. Sudborough, J. Turner, “Polynomial Time Algorithms for the Min Cut Linear Arrangement Problem on Degree Restricted Trees”, Proc. 23rd Annual IEEE Foundations of Computer Science Symp. ( 1982 ).
M. R. Garey, R. L. Graham, D. S. Johnson, and D. E. Knuth, “Complexity Results for Bandwidth Minimization”, SIAM J. Applied Math. 34 ( 1978 ), pp. 477–495.
F. Gavril, “Some NP-complete Problems on Graphs”, Proc. 11th Annual Conf. on Info. Science and Systems, The Johns Hopkins University, Baltimore, Md., U.S.A., ( 1977 ), pp. 91–95.
E. M. Gurari and I. H. Sudborough, “Improved Dynamic Programming Algorithms for Bandwidth Minimization and the Min Cut Linear Arrangement Problem”, manuscript.
A. S. LaPaugh, “Recontamination Does Not Help”, manuscript, Princeton University, Computer Science Dept., Princeton, N.J., U.S.A., 1982.
T. Lengauer, “Upper and Lower Bounds on the Complexity of the Min Cut Linear Arrangement Problem on Trees”, Tech. Report TM-80-1272-9, Bell Laboratories, Murray Hill, New Jersey, U.S.A. ( 1980 ).
A. D. Lopez and H.-F. S. Law, “A Dense Gate Matrix Layout Method for MOS VLSI”, TREE Trans. on Electronic Devices, ED-27,8 ( 1980 ), pp. 1671–1675.
F. S. Makedon, C. H. Papadimitriou, and I. H. Sudborough, “Topological Bandwidth”, manuscript ( 1983 ).
N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, “The Complexity of Searching a Graph”, Proc. IEEE Foundations of Computer Science Symp. ( 1981 ), pp. 376–385.
T. Ohtsuki, H. Mori, E. S. Kuh, T. Kashiwabara, and T. Fujisawa, “One-Dimensional Logic Gate Assignments and Interval Graphs”, IEEE Trans. on Circuits and Systems, CAS-26,9 ( 1979 ), pp. 675–684.
T. D. Parsons, “Pursuit Evasion in a Graph”, Theory and Applications of Graphs, Y. Alavi and D. R. Lick, eds., Springer Verlag, Berlin ( 1976 ), pp. 426–441.
J. B. Saxe, “Dynamic Programming Algorithms for Recognizing Small Bandwidth Graphs”, SIAM J. Algebra and Discrete Math. ( 1980 ).
L. Stockmeyer, personal communication to M. R. Garey and D. S. Johnson, (1974), cited in Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman Publ. ( 1979 ).
S. Trimberg, “Automating Chip Layout”, IEEE Spectum ( 1982 ), pp. 38–45.
A. Weinberger, “Large Scale Integration of MDS Complex Logic: A Layout Method”, IEEE J. Solid State Circuits, SC-2 ( 1967 ), pp. 182–190.
H. Yoshizawa, H. Kawanishi, and K. Kani, “A Heuristic Procedure for Ordering MOS Arrays”, Design Automation Conference ( 1975 ), pp. 384–393.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1983 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Makedon, F.S., Sudborough, I.H. (1983). Minimizing width in linear layouts. In: Diaz, J. (eds) Automata, Languages and Programming. ICALP 1983. Lecture Notes in Computer Science, vol 154. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0036931
Download citation
DOI: https://doi.org/10.1007/BFb0036931
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-12317-0
Online ISBN: 978-3-540-40038-7
eBook Packages: Springer Book Archive