Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees. (English) Zbl 0489.68060


68R10 Graph theory (including graph drawing) in computer science
94C15 Applications of graph theory to circuits and networks
Full Text: DOI


[1] Chung, F. R. K., On linear arrangements of trees, (1980)
[2] Automatic layout of low-cost quick-turnaround random-logic custom LSI devicesProc.13th Design Automation Conf.San Francisco19767985
[3] Some NP-complete problems on graphsProc. 11th Conf. on Information Sciences and SystemsJohns Hopkins UniversityBaltimore, MD19779195
[4] Garey, MichaelR.; Johnson, DavidS., Computers and intractability, (1979) · Zbl 0411.68039
[5] Harper, L. H., Optimal assignments of numbers to vertices, J. Soc. Indust. Appl. Math., 12, 131, (1964) · Zbl 0222.94004
[6] Relationships between pebble games on directed and indirected graphsTech. Rep., Bell Laboratories, Murray Hill, NJ, 1980, Acta Informatica, to appear
[7] The space complexity of two pebble games on treesLCS Rep.133MITCambridge, MA1979
[8] Lengauer, Thomas; Tarjan, RobertE., The space complexity of pebble games on trees, Inform. Process. Lett., 10, 184, (1980) · Zbl 0449.68028
[9] Meyer auf der Heide, Friedhelm, A comparison between two variations of a pebble game on graphs, (1978) · Zbl 0413.90101
[10] Persky, G.; Deutsch, D.; Schweikert, D., LTX—a minicomputer-based system for automated LSI layout, J. Design Automat. and Fault-Tolerant Comput., 1, 217, (1977)
[11] Shiloach, Yossi, A minimum linear arrangement algorithm for undirected trees, SIAM J. Comput., 8, 15, (1979) · Zbl 0399.05021
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.