{"entities":{"Q1093373":{"pageid":1104125,"ns":120,"title":"Item:Q1093373","lastrevid":66117648,"modified":"2026-04-12T07:40:04Z","type":"item","id":"Q1093373","labels":{"en":{"language":"en","value":"Finding fundamental cycles and bridges on a tree-structured parallel computer"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4022651"}},"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":"Q1093373$09067B0D-3087-44F3-AC38-0FE588E753FA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1a2c713a21c1ef7a27fcc6102d90e05d03443a44","datavalue":{"value":{"text":"Finding fundamental cycles and bridges on a tree-structured parallel computer","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1093373$43714A8A-58C9-4E0E-8696-6A782FDAC589","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1d32f47c32e4eeb2b376479640b6b0527544b08b","datavalue":{"value":"0628.68053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093373$35352D47-FFB0-4EE2-921B-CBB598A8A0DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"02e97859883ed0309c934ed39adb2bf4cae6511a","datavalue":{"value":"10.1016/0020-0255(86)90013-7","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093373$8B65A483-6F81-4412-B158-ACD2380D45E4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"83acb26c132edffe3503227fdedd09777c685939","datavalue":{"value":{"entity-type":"item","numeric-id":1060191,"id":"Q1060191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$AFF56745-4C0A-4DBD-AE05-76528F6AC18E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c144f0fb88440afe4b13555aedcc8676a016b6d2","datavalue":{"value":{"entity-type":"item","numeric-id":70466,"id":"Q70466"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$596304B1-4D87-422D-8F6E-F3F65CD648AA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1093373$6EA17296-27E0-4A3D-B315-9E3180D291E5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eee25aaeffac48bbd00e92f749dba8142ceff703","datavalue":{"value":"We present parallel algorithms for finding fundamental cycles and bridges in a connected, undirected graph G with n vertices. The machine model that we are concerned with is a tree-structured parallel computer which combines SIMD and systolic computers in a treelike manner. Under this model, we have an \\(O(n^ 2d/p+n \\log p)\\)-time algorithm for finding fundamental cycles and an \\(O(n^ 2/p)\\)-time algorithm for finding bridges, where p (1\\(\\leq p\\leq n)\\) is the number of processing elements used and d is the depth of a breadth-first spanning tree of G.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$94AE1417-9A41-4E71-A50B-938FFFAC47C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093373$EBB7BEFA-99A2-4AEF-A9BC-E9B2D10DCDA4","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ffe63356169bf6d1a9231ed66fd6aecdae9c1a9f","datavalue":{"value":"4022651","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093373$AFA4266B-CDEF-44D1-9A7B-5F4D097AEBBD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$20DFE1E2-C6E7-40C9-8391-99D5C8813255","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c9b4b4707b24de219a3c06435844cef79475c460","datavalue":{"value":"fundamental cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$CAEC4E85-6DED-409D-A023-3A20861C1795","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0f9fd6921fb75dc82a0e4e56b104f35b0cf8770b","datavalue":{"value":"bridges","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$9AEC8C85-353E-450B-A939-C658A682D229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4e84ee48586814a40f00ca811bc22a55bf16a558","datavalue":{"value":"undirected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$621753B3-4505-4E94-9275-A311CA155F53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0d863d0e862bff8e76a2ebbb53d38df4825b24c","datavalue":{"value":"tree- structured parallel computer","type":"string"},"datatype":"string"},"type":"statement","id":"Q1093373$F8B873DF-5A27-4F27-B86D-3A2E9603BC7F","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":"Q1093373$D49D8972-8A74-4C02-95E3-CF3A92036352","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f5dc227e6d5e53fd36b3867a6f5b37495f3783a3","datavalue":{"value":"https://doi.org/10.1016/0020-0255(86)90013-7","type":"string"},"datatype":"url"},"type":"statement","id":"Q1093373$BF786107-78F5-4074-99FF-110E9BA6AF9F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b62222bbb60d2ee27ebaa3fe181f666566150df","datavalue":{"value":"W2171403673","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1093373$0792FC23-A977-491F-8F31-D50E3B0B4605","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a77240d8edc9497a339f96af8fb98d73487d2ddc","datavalue":{"value":{"entity-type":"item","numeric-id":3875355,"id":"Q3875355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$1337FD96-4E65-4144-A77C-8D66968B3B60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd6ecca6b221a68c42607dd450ab7e9cb51b1138","datavalue":{"value":{"entity-type":"item","numeric-id":3945594,"id":"Q3945594"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$5DAA3972-DAFE-4340-B54B-89761AC49F9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b87cbd3ebd3d27af7ba1ae9cfe26e8cccfba70f7","datavalue":{"value":{"entity-type":"item","numeric-id":2550626,"id":"Q2550626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$909ACC31-3980-46EF-8A32-FACEA6D0DA27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e16d1dc4052e71d6b4ce452bdd1e1e49e7dff8b","datavalue":{"value":{"entity-type":"item","numeric-id":4144192,"id":"Q4144192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$7B818DD0-407B-4DFD-B153-AA17CAB0BECD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b3dce3552dfbea64412441f1ced1f652d688fa0","datavalue":{"value":{"entity-type":"item","numeric-id":3932299,"id":"Q3932299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$8FA3BFB5-E49F-4F5A-B2DA-8298ADD809BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af2379ff21f411527265a32ed56767f2f3fce2c3","datavalue":{"value":{"entity-type":"item","numeric-id":797290,"id":"Q797290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1093373$4DF4625E-D243-41AE-AC3B-3F10713C18EF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b4a49684d0784f93d0dbbdae9dcf84b81316961","datavalue":{"value":{"entity-type":"item","numeric-id":3802645,"id":"Q3802645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"762b29d90e7606891957a4c9636cb0e15ac215a4","datavalue":{"value":{"amount":"+0.9029115438461304","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":"Q1093373$2A1F02C3-1174-487D-9A6A-4F84C57CA196","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"20598589339d3a72fc5a17ddffed959b1eb8f06a","datavalue":{"value":{"entity-type":"item","numeric-id":3335006,"id":"Q3335006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a819e7698e7bf51854025599001754d7f383fa87","datavalue":{"value":{"amount":"+0.863724410533905","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":"Q1093373$98E04527-A638-4A8B-ACDD-C9EA4766FA09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e0f7765788749e8bc46fadf34b7f86b98b4c4ad","datavalue":{"value":{"entity-type":"item","numeric-id":797290,"id":"Q797290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c1b8c3d80bbf85af09f2d648885f7b583952937","datavalue":{"value":{"amount":"+0.8605687618255615","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":"Q1093373$A54EBB48-0122-4787-9DD6-E8D5A31C1E43","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27fe3af7d370b48b90032be9374eddd63e88677c","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bef04b3fb2d7577ec90088aa2ba85c81f2a3f7a3","datavalue":{"value":{"amount":"+0.8283295035362244","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":"Q1093373$8AB17641-16C9-4266-B442-4DB261292B5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b235f16bd29fdaa88c3f309392cfb5c7efcc5802","datavalue":{"value":{"entity-type":"item","numeric-id":582120,"id":"Q582120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45cf1f0e2397b61e38f469782c5f2c995df2e1b6","datavalue":{"value":{"amount":"+0.8256514668464661","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":"Q1093373$107A5FA7-549A-46AE-BCEB-5CA503946585","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding fundamental cycles and bridges on a tree-structured parallel computer","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_fundamental_cycles_and_bridges_on_a_tree-structured_parallel_computer"}}}}}