{"entities":{"Q2778432":{"pageid":2789170,"ns":120,"title":"Item:Q2778432","lastrevid":83386898,"modified":"2026-05-07T07:29:24Z","type":"item","id":"Q2778432","labels":{"en":{"language":"en","value":"Network flow based buffer planning"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1715616"}},"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":"Q2778432$52D0184E-03B6-436D-875B-40CE8B940AFB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"802264199b179d0d2ccb50857a2ce0d1f33834b3","datavalue":{"value":{"text":"Network flow based buffer planning","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2778432$A42FFDBF-DAA7-498C-8B56-920C573FCA52","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af2e90a0a90ebd5abe7783890eb31e8f03f59b89","datavalue":{"value":"0992.68224","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2778432$307DF5FC-2724-43C9-9629-A25BA02E76A2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a6eece58d857623a81f2c97829595b8a2986f47","datavalue":{"value":"10.1016/S0167-9260(01)00015-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2778432$EFE48E39-64F0-460F-BA8F-1FBC6249B12E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1d2094c317ad22fc9cc654711e2c9f3b8e7ef9c","datavalue":{"value":{"entity-type":"item","numeric-id":2778431,"id":"Q2778431"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2778432$167D5C42-2A43-42FE-9EFD-D269EA2BE501","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":"Q2778432$AA0DF1B7-5237-41DC-B717-242A4DE98A3E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"de0bbc1f0efc0eda52d8a37720ec217ae66c93cd","datavalue":{"value":{"time":"+2002-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2778432$DC1F2640-366E-4B7F-8B0F-6580E6B2BB9A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"79b3bc872b6637176b35f9e46ac855febbf884f5","datavalue":{"value":"68W05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2778432$B167ED3E-5B83-497B-861E-1F52419539F0","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"783bd5580294803adf317ddce70df96e7dd9f4c0","datavalue":{"value":"1715616","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2778432$A06B13E4-6220-49D9-9D12-439C232F3895","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9a425bb1c3dff1cf3a5b53957167a83f54864a2d","datavalue":{"value":"buffer insertion","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$CF5917D5-8115-4037-9EF7-1759BDB8BB71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"51b88f67f7a87925ba54b18b03990ed86b4117f5","datavalue":{"value":"buffer planning","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$0E3C5576-170D-4EAD-80CA-AA9628A89F68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"929ccfbb42c576f33cbc37973bcb7ca667bd3bd2","datavalue":{"value":"CAD","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$871CBA5E-BE09-4881-8A41-6384D92198AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9527ea6265f63439699edc7d3ec8cd45a55d81c3","datavalue":{"value":"network flow","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$EA0E39E1-D9CC-433A-A14B-75FAC8419E3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c4df5c0cd246319ec98364cc18f750639d6c6e1","datavalue":{"value":"VLSI","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$886AA51A-C960-4D87-90F9-7D6EBDA5A1FD","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":"Q2778432$371EBE33-662C-4E1F-B84F-F128B0C72F81","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":"Q2778432$0EF1BDAC-878A-4872-817C-EF56270E1566","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e3ea2d443baa1a0871782a301f8ad5d1e2f6141","datavalue":{"value":"The problem of planning the locations of large number of buffers is of utmost importance in deep submicron VLSI design. Recently, [\\textit{Cong, Kong}, and \\textit{Pan}, ICCAD-99, p. 358 (1999)] proposed an algorithm to directly address this problem. Given a placement of circuit blocks, a key step in is to use the free space between the circuit blocks for inserting as many buffers as possible. This step is very important because if all buffers can be inserted into existing spaces, no expansion of chip area would be needed. An effective greedy heuristic was used in for this step. In this paper, we give a polynomial-time optimal algorithm for solving the problem of inserting maximum number of buffers into the free space between the circuit blocks. In the case where the ``costs'' of placing a buffer at different locations are different, we can guarantee to insert maximum number of buffers with minimum total cost. Our algorithm is based on efficient min-cost network-flow computations.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2778432$728F16AB-A55C-4A52-8FC6-46710CEFC38F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da7600466edbcdfed260ac7c552687d3444e9430","datavalue":{"value":{"entity-type":"item","numeric-id":1977991,"id":"Q1977991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a887414bfd50a701caa687f04dad2cd31a036d94","datavalue":{"value":{"amount":"+0.763995885848999","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":"Q2778432$5BB5EFAC-3915-4769-ACB4-8B140F349910","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a7ec7670d9cc280944ae7db48a6cb0fa7c8dad05","datavalue":{"value":{"entity-type":"item","numeric-id":3437690,"id":"Q3437690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cc6418f26ff47f1e7e9c13a38e93216aa2e6c5e","datavalue":{"value":{"amount":"+0.7401147484779358","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":"Q2778432$602E3060-38B1-4BD2-9DC4-AC8A650679AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ad162401bb7b5829bb0cc3ae6eee18e1f44da40","datavalue":{"value":{"entity-type":"item","numeric-id":2267084,"id":"Q2267084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e65e3f705371521d0b7c3d6032e5bceccd81e0f","datavalue":{"value":{"amount":"+0.7389594912528992","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":"Q2778432$0312ED84-C9E2-451B-918E-4BBCBD2ED331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56520e35920f764db4321c86a13633ba3bd5e869","datavalue":{"value":{"entity-type":"item","numeric-id":5056145,"id":"Q5056145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47e0950a261333bb7298ce136d2d0dd7feca49b5","datavalue":{"value":{"amount":"+0.7343752980232239","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":"Q2778432$3B0D7333-9A64-4650-9779-0A086B24984E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a393b6313052642285cd0fd4820c70c8fd608a3d","datavalue":{"value":{"entity-type":"item","numeric-id":1767685,"id":"Q1767685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2c8c0b2c879a703b0431c59d257dcbfd9b2bf18","datavalue":{"value":{"amount":"+0.7322345972061157","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":"Q2778432$E6744A19-B416-4185-92DC-1C997599A3AF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Network flow based buffer planning","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Network_flow_based_buffer_planning"}}}}}