{"entities":{"Q5906512":{"pageid":8019155,"ns":120,"title":"Item:Q5906512","lastrevid":46326159,"modified":"2025-12-24T14:07:17Z","type":"item","id":"Q5906512","labels":{"en":{"language":"en","value":"Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 561601"}},"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":"Q5906512$2CE7C5B1-6DE1-4E7F-884E-E8E0699C112C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"242d7cd24cce059a3712ea53fa7792233a2a282f","datavalue":{"value":{"text":"Optimal parallel algorithms for coloring bounded degree graphs and finding maximal independent sets in rooted trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5906512$B314DB7A-4B7D-4341-8F41-4EAF50AAF5AA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1cf733d9290b76b6350e7c5aca1aa611133947b2","datavalue":{"value":"0803.68045","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$81629AAA-A011-4FBF-B183-9089BFFA1990","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"49a47f23d8e9f43496bd84458c0700e1d1feb363","datavalue":{"value":"10.1016/0020-0190(94)90104-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$C4ADDD0C-6B1C-4D27-9A4E-2C4898CF0A9E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6a2a4ed2a117ce4c0c6ad1480f753db1ecfce1cb","datavalue":{"value":{"entity-type":"item","numeric-id":185595,"id":"Q185595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$437FCDCE-382F-4B0B-B076-5AC4A15335C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d91d0b595fbf1f937c62dc4f3cd0ed5a98b6cbd1","datavalue":{"value":{"entity-type":"item","numeric-id":396685,"id":"Q396685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$B61551ED-1570-47B0-8274-4D858BD192E7","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":"Q5906512$CB4211E1-D161-4A39-8C43-4B86BBDBA849","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1014b4907deae7afc50440422a75986018bb5219","datavalue":{"value":{"time":"+1994-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5906512$5CAE45FA-6CFA-4C06-AE0B-F5CE3CDF4602","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b65efe51b183d0f4a672427b8171cd1e14211cba","datavalue":{"value":"68W15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$50ABA7F1-6166-435F-A32E-F9EBF00DED81","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$CB2A2004-28D9-4B6D-B726-98C96F00C7DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$96E23DF3-4A02-4CF1-8521-60659050D4B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$86C66CDD-B8A6-4292-84F2-85AEA6945733","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cf74c9deba6b2cd4f7c307f2e7a48ec24ff47fd9","datavalue":{"value":"561601","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5906512$1FA49C84-13BA-4D5A-BA2C-F47FFA65FB22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$5EC818F9-B417-4AF4-98D5-1B17A26D9BAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$017B361B-9485-447F-95DE-97870FEFEF16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc00012563a75ed0c7975e9c32d5f2d16f0982e3","datavalue":{"value":"optimal algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$86696BF3-3729-4FA7-9DE4-2562759B311C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$3D5E0A89-EA8A-4BB6-BAAB-5F80B557989C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f0de1c9f116b71d20e00b93e07300eed544fdd8","datavalue":{"value":"EREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$DB5D743A-2A8A-4400-817B-3E3DCDAA4E3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34f1528cd9548b088936bf54fdf77b3eb118e9bc","datavalue":{"value":"CREW PRAM","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$FD36EAFE-286A-45E3-9364-6AAF57F2740C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"62f0a460613792c7b1d98ca7c82b87b4b903b963","datavalue":{"value":"rooted tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q5906512$087944CD-8305-4305-8F63-97FE16F61E7A","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":"Q5906512$8548F4A1-F71A-4830-A9B8-C23913C86CAF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fede85b5bb7a53868caf1d71f7f8dbd8f46c5f35","datavalue":{"value":{"entity-type":"item","numeric-id":1184985,"id":"Q1184985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$0A82D690-63A0-43FF-8AB9-B50C5DF0B90A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fcae8c1ed4dd43a3368176a28c03c6c8aba2ae59","datavalue":{"value":{"entity-type":"item","numeric-id":808699,"id":"Q808699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$4ACC9FAE-E41E-42F5-A0D0-F1C715F745A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7d664273a45028f8303ed3135b7eb7b45763d0f","datavalue":{"value":{"entity-type":"item","numeric-id":1175944,"id":"Q1175944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$09C25BB4-EC2F-4914-8C21-14DA9A142002","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f1c5a96890a21e10169edc66df7fd407f84f079a","datavalue":{"value":{"entity-type":"item","numeric-id":1825647,"id":"Q1825647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$9E346DAA-8EDE-4C7D-AD73-09863FE93713","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3a83a467a5444a1ba4b7186428b14653739e09ad","datavalue":{"value":{"entity-type":"item","numeric-id":3835033,"id":"Q3835033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$E98E9080-5712-4557-8B5D-D71AD758AC32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c5582edcb580b7fc2c266e281cd60ce272299ed","datavalue":{"value":{"entity-type":"item","numeric-id":1186596,"id":"Q1186596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5906512$6C739F51-8F3D-4D00-ACE1-F60EE37F80C7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9340485ac4c60ccf44e035bfdf1349de9cb486b","datavalue":{"value":{"entity-type":"item","numeric-id":5894617,"id":"Q5894617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e0e3d9dfa34838edab366d16e4b30aea65721c3b","datavalue":{"value":{"amount":"+0.9991658329963684","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":"Q5906512$72C43E41-16C2-4978-90D8-489CD2DA956C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c2602bfcca056ee4797ebb793418a19daf2f622e","datavalue":{"value":{"entity-type":"item","numeric-id":1186596,"id":"Q1186596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a9068f0e4e08279454d8ef0e8f2e4f0421795eb","datavalue":{"value":{"amount":"+0.9078981876373292","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":"Q5906512$F68188E5-D6D0-460E-A7F3-8E9E21BF89A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9518478db4e03109f700da3932d71267ce1543a7","datavalue":{"value":{"entity-type":"item","numeric-id":3979273,"id":"Q3979273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1eb9d8c6499feaa17e27473e69e51c311ba1bfd7","datavalue":{"value":{"amount":"+0.8821823000907898","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":"Q5906512$3B79F247-F7FC-4CF2-A18B-2EF94029D652","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5906512","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5906512"}}}}}