{"entities":{"Q4645742":{"pageid":6675323,"ns":120,"title":"Item:Q4645742","lastrevid":55898818,"modified":"2026-02-20T23:20:52Z","type":"item","id":"Q4645742","labels":{"en":{"language":"en","value":"From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6999991"}},"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":"Q4645742$9371DAAA-7FE2-4422-87C4-E785126FA817","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e55e985b5c979c3aa54c7924f993007f7e9636d8","datavalue":{"value":{"text":"From SAT to Maximum Independent Set: A New Approach to Characterize Tractable Classes","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4645742$7BD30178-9894-4573-83EC-2E7BB3F6591C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c38b71a9ddbc331cff800c253afd0cbf1efa1b8e","datavalue":{"value":"1403.68073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$0BC5CFC6-6266-46D2-AFBD-4571A6D6EDDB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"17d196a20a1a590790a50e6a6503d1a00fab4a7d","datavalue":{"value":{"entity-type":"item","numeric-id":4645741,"id":"Q4645741"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645742$0987E08F-CE17-4701-B939-1538EA4056DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"24a1d5a8e56d6b30e8a20d7354b7c9976e279101","datavalue":{"value":{"entity-type":"item","numeric-id":427559,"id":"Q427559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645742$DABB031B-1B2D-4C54-BDEA-404C7B609ECF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0618ef01335eda4cb324f37481152385c7ce02d6","datavalue":{"value":{"entity-type":"item","numeric-id":262132,"id":"Q262132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645742$59EAEA4E-EAF5-4621-BE0C-A4C254F01240","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"eae4601ff702bcaa610b94b3434abd8165930c5d","datavalue":{"value":{"entity-type":"item","numeric-id":4645721,"id":"Q4645721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4645742$E4547DCB-A2DF-4201-AC7A-B666042BF4E3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"412b474a973c0dfa7488c61fc45fdeec318e212e","datavalue":{"value":{"time":"+2019-01-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4645742$3DA94EE2-B089-475F-9D17-03EB902047B9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$65952669-05C1-4824-8187-AFE947E23238","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$C9339D94-F1EA-40C7-9086-A1820F614E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$7C13CBFB-D1BD-43BC-821D-A4007A808BF5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"7923d31972c998106911d99c2b15db793ec3c552","datavalue":{"value":"6999991","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$707BD990-DD92-4863-BC88-6B7B6B1F06F6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"232465a4b21b2442783eb000a1c43840a0e6c26c","datavalue":{"value":"maximum independent set","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645742$CE098C66-8CAB-4DD0-B974-F3B91DA552BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a0307adf3981e6daf4015e05d74e44424dc3084a","datavalue":{"value":"propositional satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645742$304F3B52-14B7-48FF-8236-9FD68EAF7C12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c299bbe79b714d8a316fe9f06676be49e51a3f49","datavalue":{"value":"tractable classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q4645742$DD877418-6A8E-490C-8FF4-A5CEC8B53AF0","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":"Q4645742$832B9F6A-1220-4391-8AD3-DB3EEA4D78D1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e7d5522c76edcb01eb4fd4661c073c7051db779","datavalue":{"value":"https://doi.org/10.29007/c9f6","type":"string"},"datatype":"url"},"type":"statement","id":"Q4645742$7D3910CB-DD62-43F5-833A-C2A6B4392A76","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"efe3d79da97aef6d72a9d45bb7020d8a1a4a7cfb","datavalue":{"value":"W4300551516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$9E8E3534-FED6-42C1-8A64-06829B2FE034","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a91c2868b01cc637d2e59565306461278f6d6995","datavalue":{"value":"10.29007/C9F6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4645742$18B39470-A097-425A-A029-47A58880FE0B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"96c220e52aabf66b9e42d430ff065ca6207dc23a","datavalue":{"value":{"entity-type":"item","numeric-id":3192058,"id":"Q3192058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3a01f265375383c4b0d20673dc2e628ad4a3084","datavalue":{"value":{"amount":"+0.8779394","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":"Q4645742$6FBBD5BD-F7A1-4158-B16A-5A51768E3112","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"580d93ea5c3fd00861f11b0907115234c84cfdc6","datavalue":{"value":{"entity-type":"item","numeric-id":1776199,"id":"Q1776199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4d34840bef9da197e27a3a233d6114f75b6b1475","datavalue":{"value":{"amount":"+0.86990213","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":"Q4645742$81B3A395-CC4B-4FD2-A43A-0737D3BB3270","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e3d8fce6b46784c4f4c3baf44be5de08c07d2e2","datavalue":{"value":{"entity-type":"item","numeric-id":2434567,"id":"Q2434567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4147d7240fdc98f7b022da4767d05fc2d431344","datavalue":{"value":{"amount":"+0.8648453","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":"Q4645742$4A299DD3-E2CF-4593-8F7C-1AFCFDD3F68B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1f61cb3cf8931f66f627088ef5a9d011e6b25b27","datavalue":{"value":{"entity-type":"item","numeric-id":2980924,"id":"Q2980924"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a46d2b44ef7ca44fd8f3c055f3243d89da6fa2c","datavalue":{"value":{"amount":"+0.8611125","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":"Q4645742$C6FCE11B-0D96-4C20-B805-F182077EFCE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2e2f72e9d4b2fdc14ab371fae47941b7994980d9","datavalue":{"value":{"entity-type":"item","numeric-id":5457273,"id":"Q5457273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1bd6576a9e95798e905b3e8c924a1e74e9793f80","datavalue":{"value":{"amount":"+0.8601355","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":"Q4645742$A4653CAF-CE1C-42C6-AF8F-F5E3C40F1CC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5fd9d18b9d035c456a6fd2708f3e7662fe7d889b","datavalue":{"value":{"entity-type":"item","numeric-id":4526965,"id":"Q4526965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c79b9e052ae2ba4780a1b4f80c55b99497e0a6ed","datavalue":{"value":{"amount":"+0.85958916","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":"Q4645742$7D3DA23B-6EAD-461D-BCFE-C77C6EE2922E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe5996d46a69aea0faebcd39d52ae3795adae448","datavalue":{"value":{"entity-type":"item","numeric-id":3225865,"id":"Q3225865"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28fad78949c20cab937c49b7d721b5b91617c563","datavalue":{"value":{"amount":"+0.8577169","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":"Q4645742$754E517C-8087-4291-B055-7B5CE39F3839","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"619e4323b381785d20cfe7699dd840f731579a79","datavalue":{"value":{"entity-type":"item","numeric-id":5092559,"id":"Q5092559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbe3bd6b0fff37765514555639b8780553c43683","datavalue":{"value":{"amount":"+0.8576987","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":"Q4645742$691DAEC7-B6B5-40D0-8C6B-A3213C202D1A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4645742","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4645742"}}}}}