A polynomial algorithm for the min-cut linear arrangement of trees

ABSTRACT

An algorithm is presented that finds a min-cut linear arrangement of a tree in O(n log n) time. An extension of the algorithm determines the number of pebbles needed to play the black and white pebble game on a tree.

REFERENCES

• 1: BRENT, R.P., AND KUNG, H.T.On the area of binary tree layouts. Inf. Proc. Lett. 11 (1980), 44-46.
• 2: CHUNG, F. R. K.some problems and results in labelings of graphs. In The Theory and Applications of Graphs, G. Chartrand, ed. Wiley, New York, 1981, pp. 255-263.
• 3: CHUNG, F. R. K.On the cutwidth and the topological bandwidth of a tree. SIAM J. Alg. Disc. Meth., to appear.
• 4: CHUNG, F.R.K. On optimal linear arrangements of trees. Comput. Math. Applic. 10 (1984), 43-60.
• 5: CHUNG, M., MAKEDON, F., SUDBOROUGH, I.H., AND TURNER, J. Polynomial tile algorithms for the min cut problem on degree restricted trees. In Proceedings of the 23rd Annual Symposium on the Foundations of Computer Science. IEEE, New York, 1982, pp. 262-271.
• 6: COOK, S.A., AND SETHI, R. Storage requirements for deterministic polynomial finite recognizable languages. J. Comput. Syst. Sci. 13 (1976), 25-37.
• 7: DOLEV, D., AND TRICKEY, H. Embedding a tree on a line. IBM tech. rep. RJ3368, IBM, San Jose, Calif., 1982.
• 8: A. Feller, Automatic layout of low-cost quick-turnaround random-logic custom LSI devices, Proceedings of the 13th conference on Design automation, p.79-85, June 28-30, 1976, San Francisco, California, United States [doi>10.1145/800146.804799]
• 9: Michael J. Fischer , Michael S. Paterson, Optimal tree layout (Preliminary Version), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.177-189, April 28-30, 1980, Los Angeles, California, United States [doi>10.1145/800141.804665]
• 10: FOSTER, M.J., AND KUNG, H.T. Recognizing regular languages with programmable building blocks. In VLSI-81, J. P. Gray, ed. Academic Press, Orlando, Fla., 1981, pp. 75-84.
• 11: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 12: GAREY, M. R., GRAHAM, R. L., JOHNSON, D. S., AND KNUTH, D. Complexity results for bandwidth minimization. SlAM J. Appl. Math. 34 (1978), 477-495.
• 13: GAVRIL, F. Some NP-complete problems on graphs. In Proceedings of the llth Conference on Information Sciences and Systems. Johns Hopkins University, Baltimore, Md., 1977, pp. 91-95.
• 13a: GILBERT, J.R., LENGAUER, T., AND TARJAN, R.E. The pebbling problem is complete in polynomial space. SIAM J. Comput. 9, 3 (1980), 513-525.
• 14: GOLBERG, M., AND KLIPKER, I. An algorithm of a minimal placing of a tree on the line. Sakharth. SSR Mech. Acad. Moambe 83 (1976), 553-556.
• 15: LEISERSON, C.E. Area-efficient graph layouts (for VLSI). In Proceedings of the 21st Annual Symposium on Foundations of Computer Science. IEEE, New York, 1980, pp. 270-281.
• 16: LENGAUER, T. Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees. SIAM J. Alg. Disc. Meth. 3 (1982), 99-113.
• 17: LENGAUER, T. Black-white pebbles and graph separation. AT&T Bell Laboratory Memorandum. AT&T Bell Laboratories, Murray Hill, N.J.
• 18: LENGAUER, T., AND TARjAN, R.E. The space complexity of pebble games on trees. Inf. Proc. Lett. 10(1980), 184-188.
• 19: LOUI, M.C. The space complexity of two pebble games on trees. LCS rep. No. 133, M.I.T., Cambridge, Mass., 1979.
• 20: Fillia Makedon , Ivan Hal Sudborough, Minimizing Width in Linear Layouts, Proceedings of the 10th Colloquium on Automata, Languages and Programming, p.478-490, July 18-22, 1983
• 21: MAKEDON, F., PAPADIMITRIOU, C.H., AND SUDBOROUGH, I.H. Topological bandwidth. SIAM J. Alg. Disc. Meth. to appear.
• 22: MEGGIDO, N., HAKIMI, S. L., GAREY, M. R., JOHNSON, D. S., PAPADIMITRIOU, C.H. The complexity of searching a graph. In Proceedings of the 12th Annual Symposium on Foundations of Computer Science. IEEE, New York, 1981, pp. 376-385.
• 23: MEYER AUF DER HEIDE, F. A comparison between two variations of a pebble game on graphs. Theor. Comput. Sci, 13 ( 1981 ), 315-322.
• 24: PERSKY, G., DEUTSCH, D., AND SCHWEIKERT, D. LTX-A minicomputer-based system for automated LSI layout. J. Des. Autom. Fault Tolerant Comput. 1 (1977) 217-255.
• 25: SHILOACH, Y. A minimum linear arrangement algorithm for undirected trees. SIAM J. Comput. 8 (1979), 15-32.
• 26: VALIANT, L.G. Universality considerations in VLSI circuits. IEEE Trans. Comput. C-30, 2 (198 I), 135-140.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Design, Measurement, Performance, Theory, Verification