{"entities":{"Q834937":{"pageid":836785,"ns":120,"title":"Item:Q834937","lastrevid":64726155,"modified":"2026-04-11T21:49:27Z","type":"item","id":"Q834937","labels":{"en":{"language":"en","value":"A simple proof that finding a maximal independent set in a graph is in NC"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5599154"}},"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":"Q834937$3209D0D6-29D5-462F-8F85-CC114ED8C6F2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9a46c353399e24ad987dcf9c5b80c397e085f254","datavalue":{"value":{"text":"A simple proof that finding a maximal independent set in a graph is in NC","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q834937$6E6C2E92-18A2-4834-9FC7-98F023768925","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8ea81d431779a2421f3839296ef0aa8480ee482e","datavalue":{"value":"1173.68851","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q834937$8E5455AA-FE5A-4B7F-8D29-0041A572FC6A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5ee20fce6c62131399e2cc1c08173b52be3b1be1","datavalue":{"value":{"entity-type":"item","numeric-id":834936,"id":"Q834936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q834937$D8C9B1D7-F26A-4F53-821D-17E8E20D6694","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":"Q834937$6EDDC242-7962-452B-B855-EAF45C2B9733","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"53d537450d777afe86620348ba62a2bca3ff92d2","datavalue":{"value":{"time":"+2009-08-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q834937$8079ED07-C9F9-43F7-8046-112BD5F7F6ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de3565cfd3393000dd87ca545f95ff84d4c1446","datavalue":{"value":"68W10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q834937$BBDC3F1E-1A35-435B-9538-4CC9EB535F46","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1b1c2d99291e8806bdd4c2d30aa193a130276a56","datavalue":{"value":"5599154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q834937$C744DBB9-0E4C-401A-A6E2-A33A9E8B846F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d33669a46e6c8e8b36873d1f752821b7694a60c9","datavalue":{"value":"parallel algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q834937$AAAA1C7B-9E27-43FA-87AD-4048A1A1C7E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed3b495ba8c3c3bf5babb1d3213a6c0bf58078e5","datavalue":{"value":"graph algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q834937$6D36946E-FF1A-4BC4-9AB1-FC3B8822E941","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7ae5cad662cee9457a0e88de5ca640ccabb9ba00","datavalue":{"value":"maximal independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q834937$1D2B83CE-BF6A-4F64-90B2-A6B2B219E73C","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":"Q834937$5B0526CD-D62D-4D3C-9CC8-2E486DCD7CE9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"108db18644b7c08cade880f04959889980a8e47e","datavalue":{"value":"https://doi.org/10.1016/j.ipl.2004.08.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q834937$7FF4F7AF-2ECF-4387-942E-8F6BE39891D2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e66785a0c23f8f1e6b08872d60fba625a4a7c54c","datavalue":{"value":"W1990497205","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q834937$013A09DC-3DB3-4BDE-85CC-ABE07E87D77F","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":"Q834937$82462EC4-008A-42F4-A697-23EB78B80FA1","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":"Q834937$31849B4F-16A4-41EB-ABF4-DD6C07C28023","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d788a18fb1a9d69dbab97c11017e990fe408187","datavalue":{"value":{"entity-type":"item","numeric-id":3136616,"id":"Q3136616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q834937$DE0D0A9D-5EDB-49EB-8869-4099FCE72AA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f8274bc2d0aa37377844e5a10f761913ca30660","datavalue":{"value":{"entity-type":"item","numeric-id":2709793,"id":"Q2709793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q834937$DD8206A9-F4F6-4589-84BD-9D69AC090B64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee77505f29649c24a657424f3dfd6852fee0eca1","datavalue":{"value":{"entity-type":"item","numeric-id":3771607,"id":"Q3771607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q834937$DBE59CF1-E741-467C-8350-330F87940E99","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":"Q834937$6B6EE11B-A5B6-48EE-8349-D218615E50F8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"da1d278f96bad0b49387552a602c22fe016dc485","datavalue":{"value":"10.1016/J.IPL.2004.08.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q834937$45016936-DD59-4553-AD67-EA90B6E1BDFC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"57d4f3cdefed8eea1f683271dfc17db9a4e32574","datavalue":{"value":{"entity-type":"item","numeric-id":1350189,"id":"Q1350189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91e2f3024f4e97a48f802f784fac7644a77a4574","datavalue":{"value":{"amount":"+0.89347357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$44DD660A-56CE-4BEF-89AB-E75F7F27F04D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46ecb1c65ea20ce9b5e975f03fd4d5cf38486dd6","datavalue":{"value":{"entity-type":"item","numeric-id":3527533,"id":"Q3527533"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dac36194ee00d56b265bceed459aa4ba90995542","datavalue":{"value":{"amount":"+0.8880468","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$40B373F9-A3AA-4058-A8C1-C37E429F15CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"03ba1b8edf5ad983399419a7c542009b7c9eadde","datavalue":{"value":{"entity-type":"item","numeric-id":5403002,"id":"Q5403002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96606d3c43459a5ba4ab8b1312dc4ecfa616ab89","datavalue":{"value":{"amount":"+0.87920845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$21834DB2-F93E-45F5-8270-0041885981D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d853b5e94dd9fbbc6c3070b7aaf8954467a5a89","datavalue":{"value":{"entity-type":"item","numeric-id":5301767,"id":"Q5301767"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a148f41514ad3fe673813dae363d43e6c6f4737f","datavalue":{"value":{"amount":"+0.8786108","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$080EC631-DA45-4CF1-8943-3F3814EA7202","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0febaca684741081d2df7d337e9fdd7e6ba8e17e","datavalue":{"value":{"entity-type":"item","numeric-id":673069,"id":"Q673069"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1415cce4f8ddacaddaab6f80b2ebd8adc5036e91","datavalue":{"value":{"amount":"+0.87822276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$F12678E3-5FA1-4DE3-A7E9-597378E80A61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d3066f114f97e47ce3238f743ffa601e2aaee6d","datavalue":{"value":{"entity-type":"item","numeric-id":5439059,"id":"Q5439059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"849d8d65d00474decef377e3c9e7cdd05ed50b9c","datavalue":{"value":{"amount":"+0.8771677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$83AE40F1-B25A-45EF-ABF2-99906399A8A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74c6d0f7b7afa943917c8f217213b92f928dc613","datavalue":{"value":{"entity-type":"item","numeric-id":4284106,"id":"Q4284106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f13555807ab5ce6bfc739c130a214ea164c3fb58","datavalue":{"value":{"amount":"+0.87116486","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$95D1D02A-8D53-4779-AC59-6A48A70B897E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7c39ba7184e7c4bf0d9f6824849ecb53ae07b5e","datavalue":{"value":{"entity-type":"item","numeric-id":1684927,"id":"Q1684927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4df8a154ae80d2139f1ba0d378eccd8a458c9c1f","datavalue":{"value":{"amount":"+0.8709523","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$E6A60C2E-DB93-4302-B09D-975AAA2B0E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"093c9c4679809f31a1b5b1cb4b05ff5a03f8173c","datavalue":{"value":{"entity-type":"item","numeric-id":778157,"id":"Q778157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55d387ed8059651bb8907790734e6dfe67e1401f","datavalue":{"value":{"amount":"+0.8708216","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$C7CF872C-2F51-4A45-AC61-BE6365C66A44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42ee20c886ab4b2ce0f93961988bc3942bfa0ae6","datavalue":{"value":{"entity-type":"item","numeric-id":2674559,"id":"Q2674559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02b88b50b9382a0c0d46d0078fb2127353dcbe82","datavalue":{"value":{"amount":"+0.8705146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q834937$F187F1BD-28EA-42F4-8BFB-6A677269F0FC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A simple proof that finding a maximal independent set in a graph is in NC","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_simple_proof_that_finding_a_maximal_independent_set_in_a_graph_is_in_NC"}}}}}