{"entities":{"Q1072703":{"pageid":1083455,"ns":120,"title":"Item:Q1072703","lastrevid":69570006,"modified":"2026-04-13T07:54:42Z","type":"item","id":"Q1072703","labels":{"en":{"language":"en","value":"Lower bounds on parallel algorithms for finding the first maximal independent set"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3943029"}},"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":"Q1072703$90EE73F6-0659-47E7-BA87-8D44C006F67E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"13a3975208215e96744d73cbaac170ee7f757e16","datavalue":{"value":{"text":"Lower bounds on parallel algorithms for finding the first maximal independent set","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1072703$6A06EA72-B8F9-4140-919D-75D1D3E9EB8A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b06702cae61d6211e7ec590478c52c17d3f81364","datavalue":{"value":"0587.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072703$E55D915D-F2A0-4E7C-8C0C-CE950B8413AB","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92fdcb7eff17d58992ec6d6f20243318e3ee7cd8","datavalue":{"value":"10.1016/0020-0190(86)90145-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072703$4E9FEE4E-B038-46EB-B025-7208F26A86D3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"855d8872a495aa24469c23359eec4865d90d55e0","datavalue":{"value":{"entity-type":"item","numeric-id":1062625,"id":"Q1062625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072703$BC187CDB-D0B7-46A6-A437-8CE4184D8117","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072703$41D06346-6CD2-4B5C-8337-28E4996B8141","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":"Q1072703$579FE62A-DBD8-4E01-A980-BD5C8239DFDC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"425c627b3797003c91b8a656f427ca6e49470923","datavalue":{"value":"In this paper we introduce a model of computation using oracles which allows us to consider a class of problems which involve selecting a subset of a set of elements. This class can be solved in linear sequential time, but we prove that any deterministic or probabilistic parallel algorithm using p processors can achieve a speedup of at most O(log p). In addition, we prove that any algorithm that solves this class of problems must have a specific sequential structure.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072703$66782148-7946-4D62-8EAF-17143C5812B0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072703$BF94AB5E-75F1-46ED-93DC-78EB1EC2C587","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d2b3192e190a0c8086138742dd06ca3b24aafeef","datavalue":{"value":"3943029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072703$6156594E-F084-44CC-9CDE-8BCB11EFD319","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"741d3a5fca1fb52e392d264e84a73b63feda5c80","datavalue":{"value":"independence system","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072703$B883CFAD-46BB-466D-81B0-ECFC96549500","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"431ad0527b194c43bf7b26fc7f3a3705c49e72a4","datavalue":{"value":"parallel computation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072703$E40CCD3C-72B0-440D-B4AF-6E01238BF45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8c912dd45456959aa9594fa8a89e3f787ad398ae","datavalue":{"value":"oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1072703$D471E324-82FA-42C7-9CAD-4D74B6F6B2DE","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":"Q1072703$861294FF-75A6-4272-B5CC-55D3AA7A3AAE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7fd6c8694e6083e8596397eb6205454ea955b5b7","datavalue":{"value":"https://doi.org/10.1016/0020-0190(86)90145-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1072703$EFBDD6A8-3AE0-4805-A36A-9797726F8FC6","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cbab045741a4b46bdf10da50a4e90593bbfa28f6","datavalue":{"value":"W1965151869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1072703$66093A2C-FA7F-4EE9-877F-9107D1806DE8","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"105a42b9d963cd1fb6e3de311b73c6eb9ace9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4069777,"id":"Q4069777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1072703$BDA63BF7-0CCF-4E17-BFF8-4BC752811B64","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3e22f819fa331f56b3005547b547a1c09e6aca7","datavalue":{"value":{"entity-type":"item","numeric-id":3835033,"id":"Q3835033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea91ed9d990ee02a73fb9f6ca84492c34567483b","datavalue":{"value":{"amount":"+0.792399525642395","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":"Q1072703$4B37936D-D02E-4B5B-8CF6-84631C5C8C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a453761894a408c2632741908bd24f2fc41a00fe","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f574525027fe2f227a9c8f3f646945d211d648e","datavalue":{"value":{"amount":"+0.7868410348892212","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":"Q1072703$E2511A69-01F7-4EE7-8F7F-D09CE6188109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dc563087439fec342cb7cb4f34d8fdadf81f6b0","datavalue":{"value":{"entity-type":"item","numeric-id":3768419,"id":"Q3768419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1459bf319b529da9f70b8e5d5fb39a33d0ec0c6","datavalue":{"value":{"amount":"+0.7780609726905823","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":"Q1072703$8B595ADF-74EF-4DCE-8F96-EE20C5952A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"50e3138cc37b7ed9df3db17168ab00f9733f3f9f","datavalue":{"value":{"entity-type":"item","numeric-id":4694725,"id":"Q4694725"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d1cf65b1f9e2cc7f6febe25ea9213f50587aa08b","datavalue":{"value":{"amount":"+0.7723318338394165","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":"Q1072703$A81F57BC-B551-4038-A184-869AC8860D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad24f8b4046a59c89cb8d1f22be46302f90cf4fa","datavalue":{"value":{"entity-type":"item","numeric-id":4729373,"id":"Q4729373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f916319c4a61ad335834f0e1c93ed513f4f860c0","datavalue":{"value":{"amount":"+0.7707234025001526","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":"Q1072703$A9817AD6-49D8-456A-BBB4-C3C8635C9692","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lower bounds on parallel algorithms for finding the first maximal independent set","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lower_bounds_on_parallel_algorithms_for_finding_the_first_maximal_independent_set"}}}}}