{"entities":{"Q2734604":{"pageid":2745343,"ns":120,"title":"Item:Q2734604","lastrevid":47657128,"modified":"2026-01-02T08:48:53Z","type":"item","id":"Q2734604","labels":{"en":{"language":"en","value":"A fast hypergraph min-cut algorithm for circuit partitioning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1634888"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2734604$2EFBF95C-2FFC-42C9-84E8-C0A9B16F0353","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"724f5cd93ee8ef23151aac13207752c684813dcc","datavalue":{"value":{"text":"A fast hypergraph min-cut algorithm for circuit partitioning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2734604$9611230B-393E-4245-86C2-37BDC89D7125","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f89e873dc16f7e2490a69e9a9af9da4bbc365cf","datavalue":{"value":"0974.68252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2734604$9A9CDEEA-9409-4351-AC97-B397CBC6C9BA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f0850432582b70bd8f444c6cc139dfd817234b6c","datavalue":{"value":"10.1016/S0167-9260(00)00008-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2734604$1D23567C-1038-409C-AB16-B8E4FB3C0EFE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2eca232fbf7b09b849c150839e31e8a674a5f847","datavalue":{"value":{"entity-type":"item","numeric-id":1306367,"id":"Q1306367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2734604$FFB5A13D-ABED-4DF1-9A4E-C8A58728ECB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"460d917bdbf67d6e19b57c128bbed85d5078c459","datavalue":{"value":{"entity-type":"item","numeric-id":237943,"id":"Q237943"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2734604$F239A728-FACC-4990-A0FC-D9586C4A6480","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2734604$842A8FD5-C934-421D-9142-51780C7045E9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3cb322112ae56aec500b334b7351f32fb107365","datavalue":{"value":"68W35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2734604$47DF4817-DFED-4E7F-BBC6-0F37243CBFC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2734604$89EB1AE8-7D64-49B5-A3F3-AC034C89BDFA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5eda7cb372aa7da7d592b54cfde8850438929c6","datavalue":{"value":"1634888","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2734604$34F60192-2B4A-4612-8CF4-AEA244885E18","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f389102b747b912f5d2a222be11f04c89a5582b","datavalue":{"value":"circuit partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$10CC48F3-D773-44EC-8ADB-DFA8ECB6403F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3fb071ed073ac4938a76d06158d8f25b449d4bce","datavalue":{"value":"minimum cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$30955E07-3D91-447D-9A53-826AA361FF64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"63a0b5bbdbffeb2f6d94dda6a7bccbc2173775aa","datavalue":{"value":"hypergraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$C8AC5D18-CAFA-4900-AA5D-55A0B0C6229E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ca916ef37c0dac662e055f917ff073e1092f2a8","datavalue":{"value":"min-cut partitioning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$0B9E756C-5068-4938-8DF3-40DD0B3B53FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d947bebe2c3cbee7526e86c6c2b06aec71c9e278","datavalue":{"value":"flow-based algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$4A47173D-6F78-4C4D-A346-4D5A0C6F4C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"38108715257596f4ef7a3d4f9ba10572a938f348","datavalue":{"value":"non-flow-based algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$67485D92-2078-4D8D-A542-FD978617D1C2","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2734604$139F0EB8-A2A1-4AE9-9CC8-C87450C6C6A5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9eb22127669c7fd34b2d687b645802a8adc7f6f4","datavalue":{"value":{"entity-type":"item","numeric-id":6769129,"id":"Q6769129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2734604$BD62C3F8-89C7-4D07-95CC-2633EB30FDEB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03c2d7ce6d0b41566a01c12714ada0f98cd1043d","datavalue":{"value":"Circuit partitioning is one of the central problems in VLSI system design. The primary objective of circuit partitioning is to minimize the number of interconnections between different components of the partitioned circuit. So the circuit partitioning problem is closely related to the minimum cut problem. Recently, two very fast algorithms for computing minimum cuts in graphs were reported [\\textit{H. Nagamochi} and \\textit{T. Ibaraki}, SIAM J. Discrete Math. 5, No. 1, 54-66 (1992; Zbl 0754.05062)]. However, it is known that a circuit netlist cannot be accurately modeled by a graph, but only by a hypergraph. In this paper, we present the fastest algorithm known today for computing a minimum cut in a hypergraph which is a non-trivial extension of the result in \\textit{M. Stoer} and \\textit{F. Wagner} [J. ACM 44, No. 4, 585-591 (1997; Zbl 0891.68071)]. Since the netlist of a circuit can be modeled naturally as a hypergraph, this opens the opportunity for finding very-high-quality solutions for the circuit partitioning problem. Unlike most minimum cut algorithms which rely on flow computations in a network, ours is a non-flow-based algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2734604$7AB03408-A8C6-4891-B297-EDB14FC7A5AC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"994fff4248371dda043cce2c7d1cf7b2a1fd49d4","datavalue":{"value":{"entity-type":"item","numeric-id":4420947,"id":"Q4420947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3851ccde44d71902e04980f7f4bc0f68cd1457f1","datavalue":{"value":{"amount":"+0.8397579789161682","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2734604$173A99C9-749E-4129-B421-A32FE099ABA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"26ed8b99cbd7c2cd6a4f6e4d297ab73a789583f5","datavalue":{"value":{"entity-type":"item","numeric-id":4028112,"id":"Q4028112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8efb8ed01c00bbad601d1da194b73ef18f8b87e","datavalue":{"value":{"amount":"+0.838935375213623","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2734604$6EF7C3E1-8B01-40F2-8694-8FCE429B26D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b55677e599783e80218dc4b769f317f4f0b62039","datavalue":{"value":{"entity-type":"item","numeric-id":1799394,"id":"Q1799394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"427f99dd35875ebb9066ec85cecfd3885aa4e28f","datavalue":{"value":{"amount":"+0.8352301716804504","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2734604$97DCE981-112A-4EC6-87A3-9304790E8984","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ea1a59aa7fef93bc8f7cb3045f123132f95b841","datavalue":{"value":{"entity-type":"item","numeric-id":3752416,"id":"Q3752416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d91dc10a94c19ca9b2cb764fc5e3b07b9d471bce","datavalue":{"value":{"amount":"+0.8158222436904907","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2734604$D5953CA4-7B22-4861-AE79-0B8E33CDE5E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"455f736c86a26aacfdf3c33331d2347908a85494","datavalue":{"value":{"entity-type":"item","numeric-id":3360809,"id":"Q3360809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f124b19403bf27bb2eaa726cf46454c535f29fcd","datavalue":{"value":{"amount":"+0.8154726028442383","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2734604$3B84FFDD-F563-426F-A615-66B1F49BB827","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2734604","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2734604"}}}}}