{"entities":{"Q1208922":{"pageid":1219671,"ns":120,"title":"Item:Q1208922","lastrevid":66880338,"modified":"2026-04-12T13:29:19Z","type":"item","id":"Q1208922","labels":{"en":{"language":"en","value":"The interconnection problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 167120"}},"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":"Q1208922$D9DA6338-DF22-401A-9870-64F78D38DA3E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6f0b3692873e0d95d5604009a34b961f67c08504","datavalue":{"value":{"text":"The interconnection problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1208922$556D7040-3C04-404F-94B7-75EF34E086EC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c289c2a6bf196c355d10b13848b6382f5be47fb","datavalue":{"value":"0776.68095","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$7F5A9332-7AD7-401C-8F86-F752D155E9C6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"93ecfd69063b79972e0aaacbc523e0ec80995cb1","datavalue":{"value":"10.1016/0022-0000(93)90047-Z","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$DF39FA50-6692-4983-BB10-4681B504D688","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":"Q1208922$8E47F9C1-4873-451D-A8A2-28DF62851537","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208922$D3EFD56E-8B99-4155-A6C1-C7775576DFAC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1208922$1C7B228D-78DF-496C-9EB2-244891430334","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a23e21c7b478cbbb31eb1592dbdf41ac9f7818e7","datavalue":{"value":"The problem of interconnecting circuit modules in microprocessor and digital system design is studied. Data transfers are described by sets \\(T_ i\\) of directed edges between the modules, for \\(1\\leq i\\leq m\\) time steps. An interconnecting schema, where data transfers are assigned to buses, consists of links between modules and buses.   First, it is shown that the problem to find an assignment with minimum number of links NP-complete. Then, the problem to find an embedding of the transfers to a given interconnection schema is studied. The problem can be solved in polynomial time, if there are only transfers with different sources for each time step. But, in general the embedding problem remains NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208922$A28B797B-C82A-4B7B-BE32-7DF8CB72E257","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":"Q1208922$0C93AAE3-FC89-412A-96C1-C7C81BC53B6E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$8F0E7707-65F4-49FD-88A2-9A0F2EF3D75C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"06aaf19f4bbdd9676f0ed308701e830d30be51c5","datavalue":{"value":"68M99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$2D30DAC2-8DAC-4AF8-95E2-73FC16D29DF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$CD3586FA-328D-4E09-8445-E7181D800C08","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ac9fb616b8fef9a5850ad132d9612793707ebb5d","datavalue":{"value":"167120","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$20DE0255-29A7-43C3-A604-C503A93495FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"178c09c9362e4e03ade2d3abeb35878f580822ce","datavalue":{"value":"bus architecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208922$96A5A208-F290-42D4-9D19-AD7C874AC3D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208922$62D6C23B-0BF8-46A1-AF5E-B3B120AC1404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67e275f4c5e3f283b692104c20347075fa270e17","datavalue":{"value":"interconnection","type":"string"},"datatype":"string"},"type":"statement","id":"Q1208922$4BC3AF30-5621-49FB-932B-2B7FD1B64880","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":"Q1208922$697609FA-E5D0-428A-8109-B4857A780F8F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef757ecac8e00102e8fe2d81d7657ee3391ff698","datavalue":{"value":{"entity-type":"item","numeric-id":4138187,"id":"Q4138187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208922$1E92F0C2-9C6A-4206-866D-4867776B29D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242f6732c9aecb9180d76230dd0b3ce80be5a4cb","datavalue":{"value":{"entity-type":"item","numeric-id":4130999,"id":"Q4130999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208922$3E52B12B-46F6-4D19-8FCA-F0267F46F803","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8666e7867111b363298a316b4b356bd96bec7a42","datavalue":{"value":{"entity-type":"item","numeric-id":4132137,"id":"Q4132137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1208922$C5A480E0-331C-4705-A4CA-AB0C98A4E17A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e4833ebf1a592a3a25669b307ad4ae41600c6a6c","datavalue":{"value":"https://doi.org/10.1016/0022-0000(93)90047-z","type":"string"},"datatype":"url"},"type":"statement","id":"Q1208922$A0A866A0-9269-4BC8-B45F-C69B52699B94","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a2f6c165a5ee394d37c7da981a7d9be5f17ac269","datavalue":{"value":"W1974887678","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1208922$D1FCC2F3-91FD-4BF3-9E98-78EC67C1BC7B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"68c4d72d832ff1ae3a5e76cf4d78ba45a84bc721","datavalue":{"value":{"entity-type":"item","numeric-id":4421174,"id":"Q4421174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb017a5772074053b99eecfdaa6fa9363ff30935","datavalue":{"value":{"amount":"+0.8546042442321777","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":"Q1208922$FB10BBE3-F184-45AB-94EC-D43F9F2A8B0F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d44bd800484591b55a960f113871604741ca80cd","datavalue":{"value":{"entity-type":"item","numeric-id":3334088,"id":"Q3334088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c973f68ac28eb6ba809d61195f48442865810fd","datavalue":{"value":{"amount":"+0.8003735542297363","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":"Q1208922$1698F168-83B7-4125-8B7E-5ED8C2AF4199","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7895b2edd0587df3da9203621f8b5c172be4da90","datavalue":{"value":{"entity-type":"item","numeric-id":3748966,"id":"Q3748966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9358e8f8d0b344cda484f82a94354334b2880664","datavalue":{"value":{"amount":"+0.7547836303710938","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":"Q1208922$F1399B15-886C-4B65-A25D-5B02F2AEA401","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07e925e1a48515630bbaedab6a0551e464244cab","datavalue":{"value":{"entity-type":"item","numeric-id":4018996,"id":"Q4018996"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"51f7edeb14b71927b2feb04b5fdc06922d1f5d9a","datavalue":{"value":{"amount":"+0.7525573968887329","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":"Q1208922$8FB195C7-88F2-4439-9366-619D6B37A873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"58da2c23b35b548c95ec5f1158eca9515c19f834","datavalue":{"value":{"entity-type":"item","numeric-id":3904539,"id":"Q3904539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"591f22d59ee087ca1e68fd92b62d60293cd2d1e8","datavalue":{"value":{"amount":"+0.7521927952766418","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":"Q1208922$2ED228A2-4E09-456A-AC44-8F13E04D8EB2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The interconnection problem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_interconnection_problem"}}}}}