{"entities":{"Q2686111":{"pageid":2696854,"ns":120,"title":"Item:Q2686111","lastrevid":57112140,"modified":"2026-03-26T16:23:14Z","type":"item","id":"Q2686111","labels":{"en":{"language":"en","value":"The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7657066"}},"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":"Q2686111$692B0AA0-2B76-4469-A5FA-652ECE4E8E30","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ed14d8b3243631c47502191c310121b6bd8b4dd9","datavalue":{"value":{"text":"The complexity of finding low chromatic spanning sub(di)graphs with prescribed connectivity properties","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2686111$3C027B3B-F616-43AE-A9B0-40538D61AFB8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$D76BF056-4EBD-4F25-9B67-F88CA2057ACE","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":"Q2686111$C3E47318-D465-4A3F-A335-1D44C2509BC8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f5c0d35ee78605f1f95b64c94cdc67c5ae5c252c","datavalue":{"value":{"time":"+2023-02-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2686111$0D1DC8AA-C69B-48AF-85DE-F29F7F26D620","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$F7609F29-0D7C-424B-9C6E-16FAC9C8F603","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$280EBF7A-FD4B-46CF-9209-D77AE5A50E3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$D61EC8DA-C994-47AF-8ADE-85D27A185CB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$87A46A9E-7182-4865-9CA7-07AC41FE5B95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$DA16FB09-1C24-4AD2-A770-35E2FCD29935","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e27f5f1d5fce482d9975147668406d05ea85558","datavalue":{"value":"7657066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$3D2B1E0D-F760-469F-B675-A3EDFE7A1DF4","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$7C6BC53D-47E9-4965-BA73-07C99667FBB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$61136C43-CB91-491D-B4C8-FA1F114C05EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$1FF4D4DA-9672-4EE0-A3F7-469659E30E68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79fea923fe257428a15567ac9a4393a98e6d9e26","datavalue":{"value":"spanning trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$EEB1AFAF-11C5-4FCD-A975-ACCBD12C6BE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4d59ad3f86c7f6069c92e92c32fdf922fe135b7","datavalue":{"value":"out-branchings","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$AF96DF08-FAAE-4B80-AA90-F41C5783B947","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q2686111$8084855D-D370-4C82-8DCC-8A14AF70EB3F","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":"Q2686111$BB99DF68-C80B-4BD2-84A0-1074A4C8AB47","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b4894ee6c589d5a87987748bdc68518b963c1fbf","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2023.113758","type":"string"},"datatype":"url"},"type":"statement","id":"Q2686111$771CBC78-9E97-40C6-8A3D-353F87267033","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ab2af68d7e9e262b220bc3b5459e894e77d546f9","datavalue":{"value":"W4319072823","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$BE4B8EC7-C726-48C6-A030-9C151A4EF380","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$85EB6CE0-BBD3-47BD-A9A9-33CB230F80A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55ebae9da9d9d2f7db8b794f8b2b885a0fa2288f","datavalue":{"value":{"entity-type":"item","numeric-id":6057659,"id":"Q6057659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$EE46708D-4256-4CA5-92DA-DA0F781C60BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a10b211d36e266aa1c8000dbc9401c4468ec9665","datavalue":{"value":{"entity-type":"item","numeric-id":5241609,"id":"Q5241609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$AB8558C3-553F-492A-B31E-E823FFCBBB3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"06404e029b4218c5e79f2429a943e468b363e320","datavalue":{"value":{"entity-type":"item","numeric-id":441857,"id":"Q441857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$A2D3F167-66AF-4BDE-955B-EB1BED0CF737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c5df05bc83b5f828f91d2699677c5b7ac22445b4","datavalue":{"value":{"entity-type":"item","numeric-id":2396159,"id":"Q2396159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$3DC9D9A3-6A37-4FD4-AB29-147627B7A492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d30d9b6cdc3526ef74b7ebc1bddf45dde96e651a","datavalue":{"value":{"entity-type":"item","numeric-id":418872,"id":"Q418872"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$ACF95BD3-EDD3-4AA5-9332-CE6B81A10733","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09bd46079448a09130919251755b98b71a6761c0","datavalue":{"value":{"entity-type":"item","numeric-id":1223314,"id":"Q1223314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$03EDBD64-FA65-4BAE-BE36-50584870D285","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4a40eec7c3892237ba8733670ebe1f5506614d1","datavalue":{"value":{"entity-type":"item","numeric-id":1229885,"id":"Q1229885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$2FE71D27-79AE-4022-B54B-69457E46D42D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"711cb68a3f23253ea3bfc5d62858e204e53a49ca","datavalue":{"value":{"entity-type":"item","numeric-id":3286077,"id":"Q3286077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$95499DE6-FC52-44A6-82E9-F17890CB5FB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a76c57ef10e9e3affeedc8e5ad90264c59b7a273","datavalue":{"value":{"entity-type":"item","numeric-id":794673,"id":"Q794673"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$CB465377-B157-4FA4-AB82-21B891EF08ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d8d99617bc2f570c5058c0385e6156853b4e78c","datavalue":{"value":{"entity-type":"item","numeric-id":4000391,"id":"Q4000391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$960AE7E3-1DD4-4F8D-9E18-5DB5AEDF1982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fdb68a6c93b064efcfd440472a9055852b0c2ec","datavalue":{"value":{"entity-type":"item","numeric-id":3275433,"id":"Q3275433"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2686111$08946E00-230B-4BE9-A58C-E64CEF034A83","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c0861822235b03908b45f4787140717b842ead08","datavalue":{"value":"10.1016/J.TCS.2023.113758","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2686111$DFCDF9A9-306D-4239-8097-13DC57AB5C39","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab19b0756ba145af4abf4e73a1c63b45486d246a","datavalue":{"value":{"entity-type":"item","numeric-id":6057659,"id":"Q6057659"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"01edc08d0fc4cb95d789fd098cbfb4a4f5ffdc8f","datavalue":{"value":{"amount":"+0.8048979043960571","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":"Q2686111$530D5B8F-2798-4577-A1F4-84D4DC64B5B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc93bd437d8e2f32ac1d01da132816a8210c0e0c","datavalue":{"value":{"entity-type":"item","numeric-id":3222861,"id":"Q3222861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de45714364e202afb965c17f0e9f6fc61bdcb156","datavalue":{"value":{"amount":"+0.8026638031005859","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":"Q2686111$A416B2E5-17B0-4199-BBBC-F6A2C1DD195E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c0c2a9869429cbb00caf801529eff965e8d8643","datavalue":{"value":{"entity-type":"item","numeric-id":441857,"id":"Q441857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b116912b300f248bfbba9cb95cc0777c7206a678","datavalue":{"value":{"amount":"+0.8011094927787781","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":"Q2686111$E4B1D348-43E0-483E-9A57-3C8A0AB48C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2639999cb3cbfa676d835949f4f99311b5a1f97a","datavalue":{"value":{"entity-type":"item","numeric-id":4210669,"id":"Q4210669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f004e82304f464c071d7e86c4d622b93c08cac6f","datavalue":{"value":{"amount":"+0.7838477492332458","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":"Q2686111$B590E762-9633-4532-80CB-0046EDBD74E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b22ac42b08f952e0ccc76f7cd8505af9361cd44","datavalue":{"value":{"entity-type":"item","numeric-id":2685331,"id":"Q2685331"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7696de0a9092b3eb91c25331a538b1a40b92ff14","datavalue":{"value":{"amount":"+0.7833760976791382","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":"Q2686111$9D6FAF23-9A08-49A0-BC45-4875A8087A3D","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":"Q2686111$8DD43D73-A7DF-43F9-81ED-02BECBA3440E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2686111","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2686111"}}}}}