{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T05:10:46Z","timestamp":1737090646102,"version":"3.33.0"},"reference-count":47,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,11]],"date-time":"2006-10-11T00:00:00Z","timestamp":1160524800000},"content-version":"vor","delay-in-days":5276,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Networks"],"published-print":{"date-parts":[[1992,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The work proposes several partitioning criteria, i.e, the flux cut<jats:italic>A<\/jats:italic>, the flux cut<jats:italic>B<\/jats:italic>, the cost ratio cut, and one generalized minimum cut. The flux cut<jats:italic>B<\/jats:italic>is an extension of the flux cut<jats:italic>A<\/jats:italic>. The cost ratio cut generates an optimal partitioning for a linear placement problem. The generalized minimum cut uses a cost function related to a polynomial function of the sizes of two partitioned subsets. A high\u2010order polynomial function tends to generate partitions such that the partitioned subsets equal specified sizes. A simplified case is the ratio cut that is shown to derive the clustering structure of the network. The physical meaning of the cuts is described. The partitioning problems are shown to be strongly related to the communication problems. Several network flow models are constructed. We illustrate relations between the maximum flow solutions and the minimum partitionings. We use linear programming to formulate the proposed maximum flow problems. The duality techniques of linear programming are utilized to derive a relation to the optimal partition solution. Thus, we have identified the cases when the optimal partition solutions can be determined in polynomial time.<\/jats:p>","DOI":"10.1002\/net.3230220307","type":"journal-article","created":{"date-parts":[[2007,5,12]],"date-time":"2007-05-12T12:22:03Z","timestamp":1178972523000},"page":"297-315","source":"Crossref","is-referenced-by-count":9,"title":["The optimal partitioning of networks"],"prefix":"10.1002","volume":"22","author":[{"given":"Chung\u2010Kuan","family":"Cheng","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,10,11]]},"reference":[{"volume-title":"Random Graphs","year":"1985","author":"Bollobas B.","key":"e_1_2_1_2_2"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"R. R.BoorstynandH.Frank Large\u2010scale network topological optimization. IEEE Trans. Commun.Jan. (1977)29\u201347.","DOI":"10.1109\/TCOM.1977.1093708"},{"key":"e_1_2_1_4_2","unstructured":"R. K.BraytonandC.McMullen The decomposition and factorization of Boolean expressions.IEEE International Symposium on Circuits and Systems(1982)."},{"volume-title":"Design Automation of Digital Systems","year":"1972","author":"Breuer M. A.","key":"e_1_2_1_5_2"},{"key":"e_1_2_1_6_2","unstructured":"R.CamposanoandR. K.Brayton Partitioning before logic synthesis.IEEE International Conference on Computer\u2010Aided Design(1987)324\u2013326."},{"key":"e_1_2_1_7_2","doi-asserted-by":"crossref","unstructured":"H. R.CharneyandD. L.Plato Efficient partitioning of components.Proceedings of the Design Automation Conference(July1968)16\u20100\u201316\u201021.","DOI":"10.1145\/800167.805401"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230170406"},{"journal-title":"Algorithmica","article-title":"Maximum concurrent flow and minimum ratio cut","author":"Cheng C. K.","key":"e_1_2_1_9_2"},{"key":"e_1_2_1_10_2","doi-asserted-by":"crossref","unstructured":"C. K.ChengandE. S.Kuh Module placement based on resistive netowrk optimization.IEEE Trans. Computer\u2010Aided Design July (1984)218\u2013225.","DOI":"10.1109\/TCAD.1984.1270078"},{"key":"e_1_2_1_11_2","doi-asserted-by":"crossref","unstructured":"C. K.ChengandY. C.Wei An improved two\u2010way partitioning algorithm with stable performance.IEEE Trans. Computer\u2010Aided Design pp.1502\u20131511 December1991.","DOI":"10.1109\/43.103500"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3829"},{"issue":"5","key":"e_1_2_1_13_2","doi-asserted-by":"crossref","first-page":"828","DOI":"10.1109\/TCAD.1987.1270326","article-title":"Simultaneous floor planning and global routing for hierarchical building\u2010block layout","volume":"6","author":"Dai W. M.","year":"1987","journal-title":"IEEE Trans. CAD"},{"key":"e_1_2_1_14_2","unstructured":"W. E.Donath Logic partitioning Physical Design Automation of VLSI Systems(B. Preas Ed.). Menlo Park CA Benjamin\/Cummings (1988)65\u201386."},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"W. E.DonathandA. J.Hoffman Lower bounds for the partitioning of graphs.IBM J. Res. Dev.(1973)420\u2013425.","DOI":"10.1147\/rd.175.0420"},{"key":"e_1_2_1_16_2","doi-asserted-by":"crossref","unstructured":"C. M.FiducciaandR. M.Mattheyses A linear time heuristic for improving network partitions.ACM\/IEEE Design Automation Conference(1982)175\u2013181.","DOI":"10.1109\/DAC.1982.1585498"},{"key":"e_1_2_1_17_2","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1956-045-5"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.5.1.97"},{"volume-title":"Computer and Intractability: A Guide to the Theory of NP\u2010Completeness","year":"1979","author":"Garey M. R.","key":"e_1_2_1_19_2"},{"key":"e_1_2_1_20_2","doi-asserted-by":"crossref","unstructured":"F.GranotandR.Hassin Multi\u2010terminal maximum flows in node\u2010capacitated networks.Discrete Appl. Math.(1986)157\u2013163.","DOI":"10.1016\/0166-218X(86)90079-X"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90031-5"},{"issue":"3","key":"e_1_2_1_22_2","first-page":"344","article-title":"Multi\u2010commodity network flows","volume":"11","author":"Hu T. C.","year":"1963","journal-title":"J. ORSA"},{"key":"e_1_2_1_23_2","unstructured":"T. C.HuandE. S.Kuh VLSI Circuit Layout Theory and Design New York IEEE Press (1985)."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.5.3.422"},{"issue":"4","key":"e_1_2_1_25_2","first-page":"697","article-title":"On an extension of the maximum flow minimum cut theorem to multicommodity flows","volume":"5","author":"Iri M.","year":"1967","journal-title":"J. Operations Res. Soc. Jpn."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"N.Karmarkar A new polynomial\u2010time algorithm for linear programming.Combinatorica(1984)373\u2013395.","DOI":"10.1007\/BF02579150"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"B. W.KernighanandS.Lin An efficient heuristic 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_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70323-6"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1969.222524"},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","unstructured":"T.LeightonandS.Rao An approximate max\u2010flow min\u2010cut theorem for uniform multicommodity flow problems with applications to approximation algorithm.IEEE Symposium on Foundations of Computer Science(1988)422\u2013431.","DOI":"10.21236\/ADA211908"},{"issue":"1","key":"e_1_2_1_31_2","first-page":"1","article-title":"Combinatorial approaches to multiflow problems","volume":"11","author":"Lomonosov M. V.","year":"1985","journal-title":"Discrete Appl. Math."},{"key":"e_1_2_1_32_2","unstructured":"M.Marek\u2010Sadowska Route planar for custom chip design.IEEE International Conference on Computer\u2010Aided Design(1986)246\u2013249."},{"key":"e_1_2_1_33_2","doi-asserted-by":"crossref","unstructured":"D. W.Matula Determining edge connectivity in O(nm).IEEE Symposium on Foundations of Computer Science(1987)249\u2013251.","DOI":"10.1109\/SFCS.1987.19"},{"key":"e_1_2_1_34_2","unstructured":"D. W.MatulaandF.Shahrokhi The maximum concurrent flow problem and sparsest cuts. Technical Report Southern Methodist University (March1986)."},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"M. C.McFarland Computer\u2010aided partitioning of behavioral hardware description. ACM\/IEEE Design Automation Conference (1983)472\u2013478.","DOI":"10.1109\/DAC.1983.1585695"},{"issue":"7","key":"e_1_2_1_36_2","first-page":"350","article-title":"A multi\u2010commodity theorem","volume":"53","author":"Onaga K.","year":"1970","journal-title":"Trans. Int. Elect. Commun. Eng. Jpn."},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCT.1971.1083312"},{"key":"e_1_2_1_38_2","unstructured":"G.Persky D. N.Deutsch andD. G.Schweikert LTX\u2010A minicomputer\u2010based system for automated LSI layout.J. Design Automation Fault Tolerant Comput. May (1977)217\u2013255."},{"key":"e_1_2_1_39_2","doi-asserted-by":"crossref","unstructured":"S.Rao Finding near optimal separators in planar graphs.IEEE Symposium on Foundations of Computer Science(1987)225\u2013237.","DOI":"10.1109\/SFCS.1987.26"},{"key":"e_1_2_1_40_2","doi-asserted-by":"crossref","unstructured":"L. A.Sanchis Multiple\u2010way network partitioning.IEEE Trans. Comput.Jan. (1989)62\u201381.","DOI":"10.1109\/12.8730"},{"key":"e_1_2_1_41_2","doi-asserted-by":"crossref","unstructured":"D. M.SchulerandE. G.Ulrich Clustering and linear placement.Proceedings of the Design Automation Workshop(1972)50\u201356.","DOI":"10.1145\/800153.804929"},{"key":"e_1_2_1_42_2","doi-asserted-by":"crossref","unstructured":"D. G.SchweikertandB. W.Kernighan A proper model for the partitioning of electrical circuits.Proceedings of the Design Automation Workshop(1972)57\u201362.","DOI":"10.1145\/800153.804930"},{"key":"e_1_2_1_43_2","unstructured":"F.ShahrokhiandD. W.Matula The maximum concurrent flow problem. Technical Report New Mexico Tech (March1986)."},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.1287\/opre.23.2.283"},{"key":"e_1_2_1_45_2","doi-asserted-by":"crossref","unstructured":"R. S.TsayandE. S.Kuh A unified approach to partitioning and placement.IEEE Trans. Circuits and Systems pp521\u2013533 May1991.","DOI":"10.1109\/31.76488"},{"key":"e_1_2_1_46_2","unstructured":"R. S.Tsay E. S.Kuh andC. P.Hsu PROUD: A fast sea\u2010of\u2010gates placement algorithm.ACM\/IEEE Design Automation Conference(1988)318\u2013323."},{"key":"e_1_2_1_47_2","unstructured":"Y. C.WeiandC. K.Cheng Towards efficient hierarchical designs by ratio cut partitioning.IEEE International Conference on Computer\u2010Aided Design(1989)298\u2013301."},{"key":"e_1_2_1_48_2","doi-asserted-by":"crossref","unstructured":"Y. C.Wei C. K.Cheng andZ.Wurman Multiple level partitioning: An application to the very large scale hardware simulator.IEEE J. Solid State CircuitsMay (1991)706\u2013716.","DOI":"10.1109\/4.78241"}],"container-title":["Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fnet.3230220307","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/net.3230220307","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:53:12Z","timestamp":1737006792000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/net.3230220307"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992,5]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1992,5]]}},"alternative-id":["10.1002\/net.3230220307"],"URL":"https:\/\/doi.org\/10.1002\/net.3230220307","archive":["Portico"],"relation":{},"ISSN":["0028-3045","1097-0037"],"issn-type":[{"type":"print","value":"0028-3045"},{"type":"electronic","value":"1097-0037"}],"subject":[],"published":{"date-parts":[[1992,5]]}}}