{"entities":{"Q5056419":{"pageid":7085996,"ns":120,"title":"Item:Q5056419","lastrevid":55918864,"modified":"2026-02-21T03:43:22Z","type":"item","id":"Q5056419","labels":{"en":{"language":"en","value":"Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7629034"}},"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":"Q5056419$1C66EA84-8E32-459A-A265-A1C52F15D6DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"56bde9e8bba55ff9fe775c6f24c0b4ce55e91531","datavalue":{"value":{"text":"Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5056419$F2E54A15-60DA-4F5B-BB80-958243DC1CC3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d00c97df105c539831e47e1cab4a0b42f142b0ab","datavalue":{"value":"1499.68264","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$8EAEB1B6-223C-4970-BBA2-727C1838EE8B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0841f46a2b7d535e4471404a40a3f6f8cd499906","datavalue":{"value":"10.1145/3450704","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$7E4F79B3-3C0E-48F6-9658-81D41C1DD08A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"76af87da259622abdeb6a2c101631a77c280fd0b","datavalue":{"value":{"entity-type":"item","numeric-id":345095,"id":"Q345095"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5056419$9B65A6A9-8D07-4E87-85A3-E06A5AA38FDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"17866e31ce7f79bb188ff1eb61febfd59ce5b4d5","datavalue":{"value":{"entity-type":"item","numeric-id":280916,"id":"Q280916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5056419$2365286B-ABA2-4975-8063-4131D8490A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d363cb3f47628078b3b27b047f92db7ec1a5ada","datavalue":{"value":{"entity-type":"item","numeric-id":300459,"id":"Q300459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5056419$12506AE8-6418-4830-9AA5-F2F03E6A9ACA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c2bda49cd00e65f0124e1bda109c33a354792bde","datavalue":{"value":{"entity-type":"item","numeric-id":280917,"id":"Q280917"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5056419$AE92F858-7520-4542-AAC9-D3EEF4EC26AB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f12bfc80fe4a431c556e028f5134a217234a7cc4","datavalue":{"value":{"entity-type":"item","numeric-id":63915,"id":"Q63915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5056419$EFFA8068-104F-4C91-AF7D-4C28CC7A3A09","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3ffbf7a5071d227412d80225c3d73ff104ccb41d","datavalue":{"value":{"time":"+2022-12-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5056419$3E0CBBEB-00AA-4CCA-B861-32E1841F26DB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$F8E34C63-31CB-4A88-AB8E-0BB0D9CCAADB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$61268BF6-040E-41AE-9FB4-D184E9735726","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$6B9C22EA-57D8-4106-B71E-254411BAE2D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"ca84c0a1de3e8c9074706ad5adbc0b1d28c30279","datavalue":{"value":"68Q27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$0F843DC7-07A8-41E7-A12C-F839B96FD9E9","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5cea55cc8fc0293af35414e426f88c1cfaf9c58e","datavalue":{"value":"7629034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$C0CDA0E5-9C41-4570-8ACD-973D7A3B5EE8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d04d7f9cc15c119b9b9d6d638f8f61fb3b9bfbd3","datavalue":{"value":"W[1]-hardness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$619DB84C-099A-490B-8D14-17FB88022F16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b0974d841ba27603503b56afd092463f7ab4b17","datavalue":{"value":"exponential time hypothesis","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$5D06F82C-9ADC-4D12-9D7C-58B2383438D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"385e815ee7366374f61789438523aa769c68dd0b","datavalue":{"value":"multiway cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$1354465B-31C4-4038-AA4B-46DFCD7758D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3888e4321007424eccfc4c0021cff8a7cf7efbc","datavalue":{"value":"multicut","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$62D37329-165A-4AFF-8F2A-2BAAE5AD3B28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00bff32c7aca5bcc8be6f76c170f7d18bfeaab9c","datavalue":{"value":"cut graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$5CD9682D-4357-4B67-A989-084F11F8DB2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f39d7fc3fc364a43a70204f0de54dd2c811a56b","datavalue":{"value":"surface","type":"string"},"datatype":"string"},"type":"statement","id":"Q5056419$8E35F108-4A42-4455-B69D-2083DC4179F5","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":"Q5056419$74293CB1-BF9E-49B9-8B2A-02EE2CFC93EF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"0886615dfbc635bcd992e09d1dfaf665ad0a9923","datavalue":{"value":"https://doi.org/10.1145/3450704","type":"string"},"datatype":"url"},"type":"statement","id":"Q5056419$D1B5C6CD-28DF-4CEA-A446-2919FA09EFDD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0fda1c7d231798b59efeb9b7547c18ead5d14a9","datavalue":{"value":"W3182693212","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$B5530F7B-D505-4086-A798-D68DBD6E60D6","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e9321d31adeac9e43a6019591b01b97d83dd76b8","datavalue":{"value":"Q130841516","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5056419$CEC33BF1-9D60-40A6-82C8-57810464C002","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc2ceae536f8e30258a4b9922b1b861a632e6ca2","datavalue":{"value":{"entity-type":"item","numeric-id":5885599,"id":"Q5885599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a94d0456f8377edfb214502166856f38275f3e3c","datavalue":{"value":{"amount":"+0.8230574131011963","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":"Q5056419$78C144FF-FF60-4B92-A97C-D8940A5A5154","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff8d9e85ab4246b197a5bfaecf0e2378d093c86d","datavalue":{"value":{"entity-type":"item","numeric-id":5743478,"id":"Q5743478"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d0da7b58abbce0f2a81c212ba24e30c1ce65010","datavalue":{"value":{"amount":"+0.7948367595672607","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":"Q5056419$5F34AC76-C68D-488F-B433-E2A6C3F60A14","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98871aac35ff0c91679dc27f8691ed2bc36f921a","datavalue":{"value":{"entity-type":"item","numeric-id":5370738,"id":"Q5370738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eddefb5afa79863fd9974900488ca277f66e96aa","datavalue":{"value":{"amount":"+0.7935352325439453","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":"Q5056419$0277BD3E-6270-4E92-83C5-537870574AC1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5056419","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5056419"}}}}}