{"entities":{"Q1109576":{"pageid":1120325,"ns":120,"title":"Item:Q1109576","lastrevid":49210114,"modified":"2026-01-06T18:47:21Z","type":"item","id":"Q1109576","labels":{"en":{"language":"en","value":"A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4070352"}},"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":"Q1109576$8617FF65-796E-40A7-B62D-0AA6E75C26F0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6534fde005c4547694199fdd2e7d3394c7be1f42","datavalue":{"value":{"text":"A nearly optimal parallel algorithm for constructing maximal independent set in planar graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1109576$63DBDA4F-40A3-4579-BB0F-B70E87795AFF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e794caea95a710fbaa57e3f4d00a39f90bbb2214","datavalue":{"value":"0655.68086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$EA8F3471-82B4-464C-9D13-4F6D66D09453","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6f1e4575ef664a25b1635f916f5262da3d8e5c2a","datavalue":{"value":"10.1016/0304-3975(88)90106-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$C0DA89F1-63DD-4D34-892C-03588BFEF0ED","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f5e3e4a8492e84e11f7f67bea925623ed4dc895c","datavalue":{"value":{"entity-type":"item","numeric-id":237645,"id":"Q237645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$5CFA0580-DA9D-4DE1-99D4-03370AC1FF37","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$D5DBC932-834C-4157-A9C3-916925A824ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1109576$9D72DD52-62DF-419E-A7A8-8A3CE4C96B05","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f503d2b8dec9f7170aadccb5634a80a057af6196","datavalue":{"value":"This paper presents an efficient parallel algorithm for constructing a maximal independent set in planar graphs. The algorithm runs in \\(O(\\log^ 2 n)\\) time with O(n) processors on a PRAM and is within an \\(O(\\log^ 2 n)\\) factor of optimal. The best previously known algorithm for this problem takes \\(O(\\log^ 2 n)\\) time with \\(O(n^ 3)\\) processors. The key subroutine of the algorithm is an O(log n) time, O(n) processor parallel algorithm for constructing a maximal independent set in a one- page planar graph. This subroutine may be of independent interest.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109576$EB00FFE0-0900-4537-894B-250AC9DD225E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$53A2E0BD-25D8-47AF-9A60-B48742DC2253","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$2FA8E465-D89F-427F-B826-142BE1F37BF3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8985afcb93e2602da50d349acf1199e9636f845a","datavalue":{"value":"4070352","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$A6F6A65F-EA7D-459B-B185-69220D008840","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0967c5f93d36d6aa18ee008d77ee288965d952b9","datavalue":{"value":"parallel algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109576$F724757A-0CE8-40B6-A134-90A4FE8C58F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a602521768d4795b8ce801eaf970fa00075370dd","datavalue":{"value":"planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109576$DB9CFE42-DE49-4DD1-B9E0-C4EB6919DCDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1109576$99C8DDCB-4030-4993-91AF-25863FAEA4BB","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":"Q1109576$BDA400F0-EE65-47BF-A179-A4C1C11FA9DD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d7f1d64406a9c4d73f427f9d23a260e482984c14","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90106-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1109576$B82347E5-AAA9-440B-B4A9-86F21523C23B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2b995a3f107a43a3de2490252706fc07702bc36d","datavalue":{"value":"W1992702935","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1109576$FD347DCA-7299-42E3-9930-B9270BDF27E6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"467979d98db9e05ef144a15cc4706cb28b6c2581","datavalue":{"value":{"entity-type":"item","numeric-id":3768419,"id":"Q3768419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$07332ED3-796E-47C5-B75E-C276E2D05DB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b90df03a170fcc85d9f6d5af38c0866a51f22b3f","datavalue":{"value":{"entity-type":"item","numeric-id":3694688,"id":"Q3694688"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$23DA31EB-FE42-4496-AD3B-B078E3612FBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1265334c97f9278fdebf22ec46b939a0e44b551","datavalue":{"value":{"entity-type":"item","numeric-id":3798262,"id":"Q3798262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$F851FAA0-0975-400C-8C4C-CDA918AC1D6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"813773fa16a57d5ba1f1f634d7f3bafad0c0476d","datavalue":{"value":{"entity-type":"item","numeric-id":3967063,"id":"Q3967063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$FC088F48-FF4D-4082-B825-C3AF7CD9FC5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b44d7fb2a6a3f5488d20530a7a8c90790e3d026e","datavalue":{"value":{"entity-type":"item","numeric-id":1252864,"id":"Q1252864"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$F3EC2A9A-D9E3-4316-9260-F50CA35D0BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a5dd87f9b47ea169d77fccc0d3b1ab0e65eb8a1","datavalue":{"value":{"entity-type":"item","numeric-id":3756533,"id":"Q3756533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$AF967AED-A44A-4855-9E01-DF75FCA7ABFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07b3023ab2e96c7839c0565934faddc8d14acbd4","datavalue":{"value":{"entity-type":"item","numeric-id":1085169,"id":"Q1085169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$7703DED9-DC1D-4DD7-A161-1DC02C08A5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a9db4a207e2ab9eef002ed1bcd0688887d186bc","datavalue":{"value":{"entity-type":"item","numeric-id":3957960,"id":"Q3957960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$8AA196AC-DD27-4D4B-AF3E-7C2FC138E028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c5477e08259683f4f1214eab272881c214067b5","datavalue":{"value":{"entity-type":"item","numeric-id":3694710,"id":"Q3694710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$0CBB8A47-4C2A-442A-A58A-9423F3BD9994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c16c0df08e375f0ed0eb72db2eb40af52a5b5c67","datavalue":{"value":{"entity-type":"item","numeric-id":3936664,"id":"Q3936664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1109576$9902E3DC-307F-45EC-B92F-652C758B6017","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57f07974b09b2e761942819e55d60d3006fd976","datavalue":{"value":{"entity-type":"item","numeric-id":913519,"id":"Q913519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7eac6c947443eb0400ec44256df581d189b2253f","datavalue":{"value":{"amount":"+0.915347456932068","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":"Q1109576$526CC51F-0473-409B-98E6-FD5E23AF98E9","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":"32f66fbb0a13c4f829f7eeb8d18dfedd143c048d","datavalue":{"value":{"amount":"+0.9000842571258545","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":"Q1109576$A4CFC2A5-BDA1-49C3-82F5-3541013B6C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91f30364f7a14b2b4f0d0fcdf509d11f5a6967d7","datavalue":{"value":{"entity-type":"item","numeric-id":808288,"id":"Q808288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc5f1a333776d3c2226fede37e0488070e72f88d","datavalue":{"value":{"amount":"+0.8870023488998413","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":"Q1109576$88E99367-2698-4B9C-9857-4C9EB4B820D3","rank":"normal"},{"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":"b53f3dcb66186775a4bc87744a942ff207863035","datavalue":{"value":{"amount":"+0.8824252486228943","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":"Q1109576$478A24A1-A9EF-47E7-9671-160C55DB705B","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":"b8036a2f5f20a7f6971424e391b5d9547f8f0bc3","datavalue":{"value":{"amount":"+0.8805088996887207","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":"Q1109576$16DF8954-FA38-4746-9A29-858234952694","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1109576","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1109576"}}}}}