{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:10:33Z","timestamp":1737090633421,"version":"3.33.0"},"reference-count":16,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":7223,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1987,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A linear placement technique that uses an objective function of the sum of wiring lengths is proposed. The method evolves from well\u2010known concepts in job sequencing and network flow. The relation between a job sequencing problem and this linear placement problem was demonstrated by Lawler. Also, Sidney proposed decomposition algorithms for job sequencing problems. Building on Lawler's and Sidney's work, we first develop a polynomial\u2010time algorithm to obtain optimal solutions for the special case of parallel graphs. Adolphson and Hu applied the max\u2010flow min\u2010cut method of the network flow problem to the partitioning of general placement problems. However, when the cut operation creates the cut of the same configuration as the previous cut operations, no additional partitioning information is obtained. We devise an optimal graph modification that tries to change the configuration of the cut for further partitioning of the problem, and achieve the maximum partitioning of the problem. Finally, a heuristic algorithm is derived to solve some Very Large Scale Integrated Circuits (VLSI) design linear placement problems. A comparison with published papers shows that our VLSI placement method produces better results.<\/jats:p>","DOI":"10.1002\/net.3230170406","type":"journal-article","created":{"date-parts":[[2007,5,11]],"date-time":"2007-05-11T22:50:21Z","timestamp":1178923821000},"page":"439-464","source":"Crossref","is-referenced-by-count":22,"title":["Linear placement algorithms and applications to VLSI design"],"prefix":"10.1002","volume":"17","author":[{"given":"Chung\u2010Kuan","family":"Cheng","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/0125042"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"C. K.ChengandE. S.Kuh Module placement based on resistive network optimization. IEEE Trans. Computer\u2010Aided Design (1984)218\u2013225.","DOI":"10.1109\/TCAD.1984.1270078"},{"key":"e_1_2_1_4_2","unstructured":"C. K.Cheng Placement Algorithms and Applications to VLSI Design Memorandum No. UCB\/ERL M84\/40 16 May.1984. Electronics Research Laboratory Univ. of California Berkeley."},{"key":"e_1_2_1_5_2","unstructured":"C. K.Cheng Decomposition algorithms for linear placement and applications to VLSI design. IEEE Int. Symposium on Circuits and Systems (1985)."},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1515\/9781400875184"},{"key":"e_1_2_1_6_3","unstructured":"Canad. J. Math. 1956 8"},{"volume-title":"Computers and Intractability\u2014A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_7_2"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/0109047"},{"key":"e_1_2_1_9_2","doi-asserted-by":"crossref","unstructured":"W. A.Horn Single\u2010machine job sequencing and treelike precedence ordering and linear delay penalties. SIAM J. Appl. Math. (1972)189\u2013202.","DOI":"10.1137\/0123021"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"S.Kang Linear ordering and application to placement. Proc. 20th Design Automation Conference (1983)457\u2013464.","DOI":"10.1109\/DAC.1983.1585693"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"B. W.KernighanandS.Lin An efficient procedure for partitioning graphs. Bell Syst. Tech. J. Feb. (1970)291\u2013307.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70323-6"},{"key":"e_1_2_1_13_2","doi-asserted-by":"crossref","unstructured":"T.Ohtsuki H. M.Mori E. S.Kuh T.Kashiwabara andT.Fujisawa One\u2010dimensional logic gate assignment and interval graphs. IEEE Trans Circuits and Systems (1979)675\u2013683.","DOI":"10.1109\/TCS.1979.1084695"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"D. M.SchulerandE. G.Ulrich Clustering and linear placement. Proc. 9th Design Automation Workshop (1972)50\u201356.","DOI":"10.1145\/800153.804929"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.2.283"},{"key":"e_1_2_1_16_2","unstructured":"O.Wing Interval\u2010graph\u2010based circuit layout. IEEE Int. Conf. on Computer\u2010Aided Design. (1983)84\u201385."}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230170406","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230170406","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:45:10Z","timestamp":1737006310000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230170406"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1987,1]]},"references-count":16,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1987,1]]}},"alternative-id":["10.1002\/net.3230170406"],"URL":"https:\/\/doi.org\/10.1002\/net.3230170406","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[1987,1]]}}}