{"entities":{"Q2408194":{"pageid":2418937,"ns":120,"title":"Item:Q2408194","lastrevid":56653167,"modified":"2026-03-18T10:16:55Z","type":"item","id":"Q2408194","labels":{"en":{"language":"en","value":"Sparsification upper and lower bounds for graph problems and not-all-equal SAT"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6788869"}},"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":"Q2408194$5D2DBFC6-93B5-4E4B-8457-9527C396D1A8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd9468326277a892c1e8f3e956a7fadcf0037f80","datavalue":{"value":{"text":"Sparsification upper and lower bounds for graph problems and not-all-equal SAT","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2408194$06016430-47EA-4CCB-818C-CFADFAE86541","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"af7a3cd2477b655bdfa567d4d4ee07010c802ded","datavalue":{"value":"1372.68129","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$E28623C7-A72A-4BF2-BFA9-2E23796DD6C4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d978dbd306dcb2b0e214f67531547820a5423530","datavalue":{"value":{"entity-type":"item","numeric-id":372969,"id":"Q372969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$E2A78D78-097C-4B32-BE0F-3DA74895392B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc26133a3fa5fc05d4da5c57a24e34948090b984","datavalue":{"value":{"entity-type":"item","numeric-id":786032,"id":"Q786032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$83DE03A2-18F8-4E5B-AE3B-B1E415F7CB78","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$8DAB613E-A010-4725-BA60-D73925F6D435","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ffb8b9712e9833c9efd07973ed7e21575a4bd2af","datavalue":{"value":{"time":"+2017-10-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":"Q2408194$AB914CA5-03F3-450F-8841-B77CC219AEDD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$B4DCA4B5-52D0-48FC-AC31-7B9684EC15FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$77DAB612-481D-4B32-A69F-C95783F2966E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$8E120BD3-5229-4BA7-9D2C-347367D4B8EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$F73B6157-5158-4E27-87AF-665417DD0625","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$9BE9425C-1CDE-4DD4-9885-D126C41A2114","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$CCC10F52-5423-49C5-A80A-52C92C81446D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d4dd7f163be452a72b48bbe08798ce1d67c0c9c2","datavalue":{"value":"6788869","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$9E9FB496-0A2D-4AE5-ACCA-84377794090D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"89064274a499b93f141ab8aab6929ae41a5ae460","datavalue":{"value":"sparsification","type":"string"},"datatype":"string"},"type":"statement","id":"Q2408194$8AC8087F-D155-4422-8BDE-B65A9A3D26E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e09726da53e95ae004a19637083ed8dc4eff896f","datavalue":{"value":"graph coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2408194$E1755CB1-723F-4D34-A8D4-36A7EE2351DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0612807c22f01764e2b3d07b2bb1c1365e520f64","datavalue":{"value":"Hamiltonian cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2408194$9F0132A3-02B0-40D0-A37F-07C86D16D690","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"252f9f9ed9fe8ca406cc19fba38a46c0414791ee","datavalue":{"value":"satisfiability","type":"string"},"datatype":"string"},"type":"statement","id":"Q2408194$3BD38A1F-A8D4-4E5B-8292-75C9E8D4E00E","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":"Q2408194$C77CC1E5-43C1-48FB-B63E-00D66C242711","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2d6ba6ddeec232d40a0e6cd50690da998bc59019","datavalue":{"value":"https://doi.org/10.1007/s00453-016-0189-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q2408194$DB3662BF-9088-4D6D-ABDA-1A36A1A27646","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b63b09bd292e76b77ad8f78462b00a308457aec0","datavalue":{"value":"W1909439116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$5FF22CEE-A62D-4F4F-B583-6014E67C5045","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"dbdfc7ab187ccc72d6b687c00da9647734c9a1bb","datavalue":{"value":"Q59513964","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$87920085-03BB-4C17-80EE-7C1A13D85277","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"41b19a3632c2026e90215c41118dbb16f94a23ae","datavalue":{"value":{"entity-type":"item","numeric-id":1034099,"id":"Q1034099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$5EDBC177-7B14-42CD-A37C-991D0CB1F75F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae02ca018e2dfff31e816dd88495963f8adf6520","datavalue":{"value":{"entity-type":"item","numeric-id":392032,"id":"Q392032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$6B03BE8E-222A-41B5-B3A3-8E0EBA56A771","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06b38574ba6bca5da0db1c75e0b34bee1c17f73f","datavalue":{"value":{"entity-type":"item","numeric-id":4979840,"id":"Q4979840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$ABAB6008-E0BB-4BCF-958F-F5BCF25572CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"301451745297abd13e42ac4f9574184f87222922","datavalue":{"value":{"entity-type":"item","numeric-id":638521,"id":"Q638521"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$CB21F86D-3DB2-4DF1-9B7D-C24CA28AE68D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d6c8003961aa88eae6dfe4b76e14c9b1bbfd40c8","datavalue":{"value":{"entity-type":"item","numeric-id":2849328,"id":"Q2849328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$1ECB6E49-10D8-411F-8008-FAF5332367B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c89c1dd5b2dd36f6dbd42be48771e8e5cf449aa","datavalue":{"value":{"entity-type":"item","numeric-id":5897987,"id":"Q5897987"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$356AB0CA-D925-49A7-8683-77EC4406BEDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e6d4df0da57fe65c0199a8d3f040854bf7ab9f82","datavalue":{"value":{"entity-type":"item","numeric-id":5743378,"id":"Q5743378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$761229C9-7C52-489B-A0A6-F74226B8ED18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2ee4c2f29e1edb2a4ed2089a87722e97005db098","datavalue":{"value":{"entity-type":"item","numeric-id":5501928,"id":"Q5501928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$30036642-91C6-4D7C-B133-7998BFFE7B84","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f05df7bb4f26ede1f7b30797fa5ddc45a0e221a","datavalue":{"value":{"entity-type":"item","numeric-id":4962171,"id":"Q4962171"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$BD9EA811-41C6-42CE-A52A-61580BBC09FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bc2f26a656de01eb00f20b27dad82d83123bad9","datavalue":{"value":{"entity-type":"item","numeric-id":4377592,"id":"Q4377592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$64ECA604-AC68-4AEC-921B-3B8D0C95AACC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f4585f4de7747ad585c10dd854396ebb3c46f01","datavalue":{"value":{"entity-type":"item","numeric-id":2828222,"id":"Q2828222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$363D529A-E4DD-4E26-AE0D-04F4A79286B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4f8578dc33f61f9f52084ab063ce58f84067974f","datavalue":{"value":{"entity-type":"item","numeric-id":619903,"id":"Q619903"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$677C8388-CA30-44C6-9C4E-2FECC546308C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$90EF24CB-E7C8-44F2-9812-E179565169F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0919fcba88d9775de644800696317266a2abf882","datavalue":{"value":{"entity-type":"item","numeric-id":5743381,"id":"Q5743381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$103FD8C2-CC2C-4D8C-BFC8-870E6867503E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4548ea5d583917c0fa9b6aaa6b1d48c80c1e7e","datavalue":{"value":{"entity-type":"item","numeric-id":1604206,"id":"Q1604206"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$2E388928-B4CC-431B-967D-42BF6315DC07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67fa83a7711b3fe6610cb008566b720bd682adec","datavalue":{"value":{"entity-type":"item","numeric-id":4608634,"id":"Q4608634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$4D17D292-058E-48D9-B2C6-BBCEFEB9B8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98fd21ce453de27d92347d4b51068d637f5f5a63","datavalue":{"value":{"entity-type":"item","numeric-id":393081,"id":"Q393081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$7600776D-BE9A-4DA9-AD4B-CFFDF99343DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$B738F508-3824-4A5B-8703-67F31CBCDB9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74d294277a463549f59bbc6fb06d14006e2c291b","datavalue":{"value":{"entity-type":"item","numeric-id":3859790,"id":"Q3859790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$6E2C87D5-83EE-4315-BE5A-4D5F0AB81577","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c2a0983ce7a664c54ed4274f83ecbe33679a4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4074668,"id":"Q4074668"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$8C2C92DC-13D1-4D64-9FCF-0C8F55845CC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d68fc7c040182999e561eed2c0b17ea838aeca6","datavalue":{"value":{"entity-type":"item","numeric-id":5635464,"id":"Q5635464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$4D19F029-C24E-47AF-8305-44F301EA85E4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"a25d7b5a0376cbcbb5a13ff8635936220a83f7ec","datavalue":{"value":"10.1007/S00453-016-0189-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$A70BA2E1-CC0D-457E-8C58-C1B2F49FBD22","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"758d5c1f85aba840e3020a1aaedc49bc8d0d1bf2","datavalue":{"value":"journals/algorithmica/JansenP17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2408194$E0D8FDA6-3E83-45DE-B52D-469AFBEC6DF5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"965c616b98ea25e09db93cacc085639d828b3bfb","datavalue":{"value":{"entity-type":"item","numeric-id":5363770,"id":"Q5363770"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5662a5da9702b138c47f7a01ab5882a0ee47efeb","datavalue":{"value":{"amount":"+0.997550904750824","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":"Q2408194$0C5D294A-75F8-469D-823A-C1EDCA02358C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d90f9a72948fa4502efb9e851a4e00a1db0fab9","datavalue":{"value":{"entity-type":"item","numeric-id":4608634,"id":"Q4608634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a09c51e8e017bf670860a0f6d3eecb89029b83bd","datavalue":{"value":{"amount":"+0.8213604092597961","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":"Q2408194$FECA9F32-5F82-439A-AF5B-117C4968772F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"706c2e7b52f58a577da252a7891ee74f91ecf61f","datavalue":{"value":{"entity-type":"item","numeric-id":5205824,"id":"Q5205824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2fa6284208fd5a60e83f4c13bb0ed7c7833bf0","datavalue":{"value":{"amount":"+0.820345401763916","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":"Q2408194$25447D4A-F9BD-4160-9F7B-A92706E58A82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e5d9a8363b139a5d68c4c494c12fbf7b679aad25","datavalue":{"value":{"entity-type":"item","numeric-id":2875151,"id":"Q2875151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a92846c4ad5382d12a293ace6fb7c99dd620c263","datavalue":{"value":{"amount":"+0.8007069230079651","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":"Q2408194$8398DC20-8B19-40F3-9623-4AB8D2777C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"23361c5083896a3b3f2e008692dfe9403693050d","datavalue":{"value":{"entity-type":"item","numeric-id":5053064,"id":"Q5053064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3ef08b8f88ab7461bd3d3154a6954c82e1adddb6","datavalue":{"value":{"amount":"+0.7928221225738525","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":"Q2408194$33EBF359-2334-4047-88C1-A7D65C9793C7","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2408194$271CEAC3-74CD-4A40-8C97-7158D7E0FAD8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2408194","badges":[]}}}}}