{"entities":{"Q1801667":{"pageid":1812409,"ns":120,"title":"Item:Q1801667","lastrevid":71291412,"modified":"2026-04-13T21:15:02Z","type":"item","id":"Q1801667","labels":{"en":{"language":"en","value":"The allocation problem in hardware design"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 205573"}},"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":"Q1801667$1DE263FA-6B85-4E5E-93A0-2397BB5880EB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6c0bc56b76f4bf3b1315ca79cf935733931bf96f","datavalue":{"value":{"text":"The allocation problem in hardware design","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1801667$9A46AAEB-E792-49D5-93EC-5A230B81D117","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"129f2e2b7fa5998dd7ff2cc1db97043cc2d610c2","datavalue":{"value":"0776.68094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$6182930F-1C1D-4880-AFBB-ECFAF4FF6537","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fd2ae794215a1c7dfa5563e7039634020e5a38e4","datavalue":{"value":"10.1016/0166-218X(93)90167-M","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$ACA2C81A-3A61-494C-B602-14ECD3D0116C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"38a47e2531a4bf8122b29daae2886484554c2a60","datavalue":{"value":{"entity-type":"item","numeric-id":243609,"id":"Q243609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$CDDE41E1-FCD4-4F19-B224-67D64419F49A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$137FD973-D865-4DD5-ADB1-5E22ECA2BFD4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f591d0602ae4e2a85ee551e3fcfd046a3335ee2b","datavalue":{"value":{"time":"+1993-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1801667$6AF8ABE1-9D7D-4733-ADDA-574CD7EE0DF8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0e9613ebf7ed1ca6372d2f16f124d00a1d6ecba2","datavalue":{"value":"In the synthesis of hardware structures different design steps are solved by combinatorial optimization techniques. In one design step, a scheduled flow graph is examined and it is determined which operations can be assigned to the same processor. The problem to look for an assignment with a minimum number of processors is equivalent to the search for a minimum coloring of the corresponding conflict graph. The graph classes of these conflict graphs are determined for the general and some special cases. Moreover, for each graph class either an optimum or an approximation algorithm is given. We notice that the studied problem is also related to another design step in high-level synthesis -- the register allocation problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801667$811E3057-CA0C-4428-BEC1-822655DBB353","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"2896e341ddc21f4043d767f7914cc0a225e28b49","datavalue":{"value":{"entity-type":"item","numeric-id":243609,"id":"Q243609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$2C619EE2-4250-48C3-8ED1-D346F169E56A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$79A9A752-5DF4-4F9D-8BD3-66075C54DE1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$93AFD3B5-F87C-4816-928C-634BFF0E0CB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"007f7f82691f1d7656215e5be329d57b0bfdf5e7","datavalue":{"value":"94C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$D7075577-7E95-4F16-93D6-93857B2D0D99","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"122cbc6d5eea7b4ed471416d58064b71e058b2b4","datavalue":{"value":"205573","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$839535BE-8D82-49DB-8924-DAE50C60B016","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60893b19873951289c4cffa4988662b3b84228a2","datavalue":{"value":"high-level synthesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801667$F1D1D41C-504A-4F93-916E-9292B1CC919E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"af13f17494cc813b4bb3df740f8de356b6dd65fa","datavalue":{"value":"register allocation problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1801667$2B091C7F-0CC5-4172-A276-53D5F81A5DCE","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":"Q1801667$E0A4F5F0-0662-4500-BC3C-0EFA4933B920","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"928176d541a5abf04d192dc43f4c69569119c705","datavalue":{"value":{"entity-type":"item","numeric-id":911757,"id":"Q911757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$5289941D-853B-45D4-8D3A-9C0C5FEF398F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f89a031afe32dfcbf4f8fba11966dba55c1408ae","datavalue":{"value":{"entity-type":"item","numeric-id":4179026,"id":"Q4179026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$1100D7CF-CC89-42CF-8E44-7543EC39DDD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$FDF13B92-FB3D-4570-AD60-A59311B45AA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$7A99FE92-A89C-40D6-BFE5-D223D21D7760","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d22d1a66627507c9e175f0940657f78d850ce78c","datavalue":{"value":{"entity-type":"item","numeric-id":3956413,"id":"Q3956413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$03967478-24CF-4B82-BDB2-E8D09A33EE2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d13b2baaeba9578e51f0f16124df9d341fafb29","datavalue":{"value":{"entity-type":"item","numeric-id":4162449,"id":"Q4162449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$1D589BC0-808E-4300-9DB2-77DCBBECAE34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b56bd3b3d97c682b91a899925d80332060ce658","datavalue":{"value":{"entity-type":"item","numeric-id":1200808,"id":"Q1200808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$E9F42B64-9393-46EC-B6DF-82F0F1C7D731","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94d4ff0ae86125fc073ba1153e5f029193cd4ff2","datavalue":{"value":{"entity-type":"item","numeric-id":4065570,"id":"Q4065570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$956B3159-8203-4A93-BC6E-6546B02BF14C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"755b705d434743289f1c33d94607b3327759f7e3","datavalue":{"value":{"entity-type":"item","numeric-id":4142699,"id":"Q4142699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$856A415B-7E0E-43E4-81DF-244EBCAA14C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28a33b862f7d8441651d4cdc6c39e4250de110d1","datavalue":{"value":{"entity-type":"item","numeric-id":2540014,"id":"Q2540014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$614C5FF8-2FB5-438A-83DB-4A73C6EFE826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef4754f01c6e5f4fbaf7f8521f5e41346da3c07f","datavalue":{"value":{"entity-type":"item","numeric-id":2563166,"id":"Q2563166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$3F58EDA3-E0D5-4459-A90B-116CC74CF2F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5da8aaede631bfdc54d481cb5dea09d28a4412b7","datavalue":{"value":{"entity-type":"item","numeric-id":3763600,"id":"Q3763600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1801667$B65A8AE5-7D64-4661-95D9-2D46ADD5A50A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6fdefba11abe79da490e8e073c9a92feb7c8cb9d","datavalue":{"value":"https://doi.org/10.1016/0166-218x(93)90167-m","type":"string"},"datatype":"url"},"type":"statement","id":"Q1801667$7CAC9678-0B1B-40EF-8579-6543BFEE03E1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fe8865462399cb28b1b4e39b8e4d14707e85eed9","datavalue":{"value":"W2014569221","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1801667$656FF182-0F2D-4551-AC20-1F97918E9B94","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed2a87d798d6a9e23c06e789695da356da0406e7","datavalue":{"value":{"entity-type":"item","numeric-id":5203657,"id":"Q5203657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de90f699196ef66110cf20c8c050b763ef1f1ea3","datavalue":{"value":{"amount":"+0.9191206","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$16C48D6F-B861-4C58-A454-2F819AAA14DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"10d4a4af6b192ce067faab04dcfd42aad35040ae","datavalue":{"value":{"entity-type":"item","numeric-id":4332004,"id":"Q4332004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c148787e9d801278773dd1b2db0208e094b94e66","datavalue":{"value":{"amount":"+0.85378486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$5AF3F6E9-646D-4DA2-9504-B2E00C4F6DFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"089f6ce040a5e156703f678167e97f5c5c68e2f3","datavalue":{"value":{"entity-type":"item","numeric-id":1286557,"id":"Q1286557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1052efde2bc0f0dd0b653403c4eaf1088854a753","datavalue":{"value":{"amount":"+0.83166903","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$1646BB72-12DF-4BE8-B187-15FAD2E4DB66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"21844a94b02ff3e9971741d35c699740c1a79cd3","datavalue":{"value":{"entity-type":"item","numeric-id":339684,"id":"Q339684"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"39033b17e011b2c6b70333f3ca13e23331eb6007","datavalue":{"value":{"amount":"+0.82870126","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$A2FE6DAA-4A83-47D7-A3CB-3AF9BC4208EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8c451b2d38dc91b1214eaeeb5b2e72e7d4e80b9","datavalue":{"value":{"entity-type":"item","numeric-id":4286721,"id":"Q4286721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fef372b4462d4a272dfd9bb45eada4a33261da6a","datavalue":{"value":{"amount":"+0.827584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$589EBDEF-73E2-48E4-BEA0-62EA25314207","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63274e331ecf9b5591d0095ebdc93459124c5f9d","datavalue":{"value":{"entity-type":"item","numeric-id":3335520,"id":"Q3335520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"252f0b112c9c43f1a3a87f710a7a00e69f9bf880","datavalue":{"value":{"amount":"+0.8272525","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$C7BCD95F-FD75-4645-8B65-855883434327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f84a659c5976b73a68269aed272b590e92071c38","datavalue":{"value":{"entity-type":"item","numeric-id":4283457,"id":"Q4283457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b39feb6250687910de671120ecf9db41dd16af45","datavalue":{"value":{"amount":"+0.8266449","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$5282D2CC-1A49-4BAE-B542-E8338B9BA516","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6673502b8fcc9bd28ee2f1f3b60a3134a8df0801","datavalue":{"value":{"entity-type":"item","numeric-id":3787468,"id":"Q3787468"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afc1449b5e425c2eb3268ad4ddebea95badc2fc7","datavalue":{"value":{"amount":"+0.82570505","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$A359249F-E32F-481B-B9DA-7244E7216EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e139d823ca30b0e1e02254cd50bd9ec5f1d42a6f","datavalue":{"value":{"entity-type":"item","numeric-id":3601928,"id":"Q3601928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48ba348cd50df3580907d39a4fb58ccfc73a1e5f","datavalue":{"value":{"amount":"+0.8237021","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1801667$B2BC0C1B-EF2B-4E72-8BAD-BB1AF2BB2E5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The allocation problem in hardware design","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_allocation_problem_in_hardware_design"}}}}}