{"entities":{"Q1111019":{"pageid":1121768,"ns":120,"title":"Item:Q1111019","lastrevid":69666864,"modified":"2026-04-13T08:34:33Z","type":"item","id":"Q1111019","labels":{"en":{"language":"en","value":"Min Cut is NP-complete for edge weighted trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4074472"}},"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":"Q1111019$1BFA938B-8DAA-4307-A247-6FC69F6D7B10","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3a899caba7d4bfce02fb204d4f64365d5f115c82","datavalue":{"value":{"text":"Min Cut is NP-complete for edge weighted trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1111019$209BE342-ED80-4B3A-96AB-80DB8E668562","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"c40b1a5cfb7e517f28a7d90901559c2a3332bd39","datavalue":{"value":"0657.68034","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$3F9020EA-A715-4B37-8015-1AD2EEFAC6D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5cafd2e18ac5077bc107bd126c8ac94e7f0e8435","datavalue":{"value":"10.1016/0304-3975(88)90028-X","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$124A4941-93EA-420B-8F9F-9AC7B65E1B44","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":"Q1111019$6B277CE0-6ACE-49E3-9E86-56D730FA6A0A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1111019$28D0A757-BE78-4D48-B25E-1102739EA323","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"eee7a407f23f16af31a76d80ce35b15237c2ead9","datavalue":{"value":"Let G be an (eventually edge-weighted) undirected graph \\(G=(V,E)\\) and L be a linear layout of G, i.e., an arrangement of the vertices of V along a horizontal line. The (weighted) cutwidth of L and G, denoted by cw(G,L), is the maximum number (weight sum) of edges connecting vertices on opposite sides of any vertical line drawn between consecutive vertices. The (weighted) cutwidth of G, denoted by cw(G), is the minimum over all (weighted) cw(G,L), L a linear layout of G. The (weighted) Min Cut problem asks whether cw(G)\\(\\leq k\\) holds for a given undirected (edge- weighted) graph G and positive integer k.    The investigation of the problem is motivated by problems of circuit design in which one wants to minimize the number of channels needed for wires connecting distinct circuit boards or gates. The weighted version may more closely model actual circuit design problems. It is known from \\textit{M. Yannakakis} [J. Assoc. Comput. Mach. 32, 950-988 (1985; Zbl 0633.68063)] that Min Cut is solvable in time O(n log n) on trees.    In this paper it is shown that    1) the Min Cut problem is NP-complete even when restricted to planar graphs with maximum vertex degree 3 and    2) the weighted Min Cut problem is NP-complete even when restricted to trees with polynomial size weights.    It is also shown that `search number' is NP-complete for planar graphs with maximum vertex degree 3 which solves an open problem described by \\textit{N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson} and \\textit{C. H. Papadimitriou} [ibid. 35, 18-44 (1988; Zbl 0637.68081)].    Furthermore the NP-completeness of vertex separation, progressive black/white pebble demand, and topological bandwidth for planar graphs with maximum degree 3 is shown.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111019$BD24683A-45DF-4EFF-B7BA-39AC6BC429ED","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$15790354-5009-42D9-9C0E-926F7E928EF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$E3CBF72F-E3A3-43FD-B77A-4607A65EBE9C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8dcb6236e4e280b207d7f33893615c41dc03604b","datavalue":{"value":"4074472","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$D6503AF8-6BA7-4015-99A0-F5708A946E16","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f809c83e643b878242c84cb516ce99fb6037dd32","datavalue":{"value":"Min Cut linear arrangement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111019$58F66745-AE80-4ECE-A01B-89D50480C66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35a10089f1f39f3dc225f467255cdd59c108808f","datavalue":{"value":"weighted trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111019$7A05C12E-FCD6-4ECC-ABB7-5BC37B0D0E9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"99fb8c69c202cd08d29b22488e32432b5a73c333","datavalue":{"value":"search number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111019$97874E84-2FAC-4CE5-9BBB-CAB1DD3383CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"57c88a7afb551d7d36a1b6cf10492f9a344cb2d3","datavalue":{"value":"NP- completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1111019$E2E7F988-510F-4543-8549-543F8E7024B3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"09a0d0982218f3bdbacd199baea5f21d14bfa873","datavalue":{"value":"Q29030082","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$11092BF0-10FC-4A73-852A-A7E501E4824C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3b9f391e6322208fe1ff9282b50ef9e948c0574c","datavalue":{"value":{"entity-type":"item","numeric-id":284584,"id":"Q284584"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$C2F88C05-94E1-4BCB-B7BE-EB4D9CB9C204","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"619555d96850b0d2a63f38f6976c99450dd5b2d1","datavalue":{"value":{"entity-type":"item","numeric-id":791315,"id":"Q791315"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$70C7B70C-FE9D-4286-8EAF-D1B09AA748EB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"5af1aa80224172db75f7ae535f0d2940793ea880","datavalue":{"value":{"entity-type":"item","numeric-id":170457,"id":"Q170457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$206CC3D5-691A-4AD1-8BBE-EFD2EB5300EE","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":"Q1111019$42D3ED0B-5B79-4D76-B17A-CEF2D0BAB02D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5890cccaa2e42ff79b9f0f2ee8067b4e5c008f8c","datavalue":{"value":{"entity-type":"item","numeric-id":3679205,"id":"Q3679205"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$E70A1AD6-7C9A-4E74-8F40-3B8857014103","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb35434071b02cad61f63c7cadd55ff55ed5a42d","datavalue":{"value":{"entity-type":"item","numeric-id":3740255,"id":"Q3740255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$7B9D5562-649A-4F3D-8FCD-8CC144F594E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038a7e4418ac17f21ed0f4437cc57844c7dfca4e","datavalue":{"value":{"entity-type":"item","numeric-id":1230508,"id":"Q1230508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$1C3BE920-9F58-4CE5-839C-544A58072B0B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f243674681d1c639e048cdd5900f8a294f117f74","datavalue":{"value":{"entity-type":"item","numeric-id":1333276,"id":"Q1333276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$3A5166A0-8B3B-4A35-A6FE-D02693BBBBAE","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":"Q1111019$48B28F88-13FD-44DA-ADE6-1549D41CC361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"93abefd43f60c4734d29bc653212ccc79b537d1c","datavalue":{"value":{"entity-type":"item","numeric-id":4165413,"id":"Q4165413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$F6A0EC41-B3BF-41CB-8C15-1930F7A11812","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"682f3840059edd7ccd7f1a5c5182d6b41ea56f03","datavalue":{"value":{"entity-type":"item","numeric-id":3906416,"id":"Q3906416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$3A88FFF7-D1B7-4AC3-91DB-D073DF77B8B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e876a74df4c5afd434282460ace786203847bd5c","datavalue":{"value":{"entity-type":"item","numeric-id":4131020,"id":"Q4131020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$9FBCEBB3-83A3-4E83-B39E-A168DCCA0E64","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"256376258f0dacc6c84417f2d334937ae797b5c7","datavalue":{"value":{"entity-type":"item","numeric-id":1821562,"id":"Q1821562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$A8A65C9F-6F10-4974-8485-E8C43186C0A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a00040d8554770d1821de600986e67f018fde51d","datavalue":{"value":{"entity-type":"item","numeric-id":3769962,"id":"Q3769962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$EB32CDE8-8E95-48D3-8AEE-29C0D8845F2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73de5d06b50821afae240d17120a93d4c93bd6f1","datavalue":{"value":{"entity-type":"item","numeric-id":5286162,"id":"Q5286162"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$9F3F7D32-84A5-4C14-B3E7-9F597BA4F897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b11d06c9a8ba95b7c44ef18e0b995059f487225c","datavalue":{"value":{"entity-type":"item","numeric-id":1149765,"id":"Q1149765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$CE4DCB0B-7B8B-41D5-BA0B-3B0D69823CD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ff8a807471958a38eef5720fd27b64677c1d24","datavalue":{"value":{"entity-type":"item","numeric-id":3869371,"id":"Q3869371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$F5CB9B5A-D2CC-495F-B8B9-957C6890FE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7240aba3392d9a3fa2165cd99316a70c1d4c7340","datavalue":{"value":{"entity-type":"item","numeric-id":1149448,"id":"Q1149448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$4A142852-CB5B-4FCA-94BA-5E370DA64009","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a36280cd96bc89546cd4961fcd5cd6aa3fbe4691","datavalue":{"value":{"entity-type":"item","numeric-id":3661483,"id":"Q3661483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$0D3B2618-BE0F-4731-BA62-2B6D05F1AA06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01ad9aadd446c6d5909b1353a38646e3156d4817","datavalue":{"value":{"entity-type":"item","numeric-id":3691781,"id":"Q3691781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$B0DDF509-81B9-4859-9553-A449482C71D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$FF8DBF03-568A-4732-BDC3-76F63335B38E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e235b1e856f674628ea45299d84fda7e204eaef1","datavalue":{"value":{"entity-type":"item","numeric-id":3208679,"id":"Q3208679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$3E6812E4-162E-44F2-AD73-60E6CBB6C12B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c30b66ff2b3993baa31f89ad45be8a5ecb924076","datavalue":{"value":{"entity-type":"item","numeric-id":1838912,"id":"Q1838912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$ABC41604-D032-4E89-9CA2-A01011396EEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"747c0c0f364bd3c246aa85c60f8a68299e9ec31d","datavalue":{"value":{"entity-type":"item","numeric-id":4092979,"id":"Q4092979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$D44E1F7D-35B3-4768-AED2-7A69D4A60AF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2479aa030f634bd795c8918a967327496f5092d5","datavalue":{"value":{"entity-type":"item","numeric-id":3771641,"id":"Q3771641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$AE3DBA9F-1DF8-48C0-87C7-8BFC446E4661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c26c1f219206a588a37699fbc3b825c5a7c6afad","datavalue":{"value":{"entity-type":"item","numeric-id":3026359,"id":"Q3026359"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$1608FF09-CF2A-4334-BF7E-1923E305B211","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"24f4aba8e0ee3a2966b3de817d74f8875ab291ae","datavalue":{"value":{"entity-type":"item","numeric-id":1223124,"id":"Q1223124"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1111019$373FE122-ACFA-45AE-8685-7C6BC40A5742","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"44f989b94038649e94a38788c21e5e551fb4178d","datavalue":{"value":"journals/tcs/MonienS88","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1111019$92B19E27-D218-4AB4-B03C-352B7D27AEDD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3e16bec71f1496a8a9d5c9c2cf73727a4c5189ac","datavalue":{"value":{"entity-type":"item","numeric-id":3725545,"id":"Q3725545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af96511b62c17c0832a876691e6dbdbf466fd403","datavalue":{"value":{"amount":"+0.9192506","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$8A438A10-4B95-4A90-8AB9-63AA82788535","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb6c6a938cb8b04a89ae2fe4d39b7397c212ff58","datavalue":{"value":{"entity-type":"item","numeric-id":3197351,"id":"Q3197351"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a4872562e0f1a8bf527b70845310f672b592de80","datavalue":{"value":{"amount":"+0.8491305","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$9F317665-C35C-48B5-9696-E6E66C1101AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d35f6527437b24afbca8d0d7c2cdcc1c391b1b0f","datavalue":{"value":{"entity-type":"item","numeric-id":3326858,"id":"Q3326858"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35c47aa5f8debb075d6585b6700b93d73e2572ab","datavalue":{"value":{"amount":"+0.84423774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$A851A4F8-A2EE-4AEA-9758-6552F9711BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1f2ff19bb212f0578317293ee8d169283cb4952","datavalue":{"value":{"entity-type":"item","numeric-id":4899245,"id":"Q4899245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65a7ff77370617e78f229c1b2ca8dee7e9a693e2","datavalue":{"value":{"amount":"+0.84348696","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$C0842A84-1050-424B-B846-8CDE6AFDC0B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd6bd9890864aa63e22111efaaf4c4dff33601dd","datavalue":{"value":{"entity-type":"item","numeric-id":813970,"id":"Q813970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e3371a77e7782150805d5f16da40e1f48b450c5","datavalue":{"value":{"amount":"+0.83387655","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$EBEC9317-4CDD-4893-90C5-A32C2DFB0A00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1b11b2b782c82c607ed56b5707d56302e5c4f4e","datavalue":{"value":{"entity-type":"item","numeric-id":1069429,"id":"Q1069429"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bb73757425c9b8623a98e5d02e6bd8d9e8b8dded","datavalue":{"value":{"amount":"+0.83133113","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$A76A9FAE-658B-4993-9622-E05A664501E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aa933d6edbc8409538f6aa43b84f87d1dd03b037","datavalue":{"value":{"entity-type":"item","numeric-id":3689216,"id":"Q3689216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4c1e9ed5df86fc388fc01dde4a94dbc3d69f5fd1","datavalue":{"value":{"amount":"+0.8281749","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$834A5480-AA1A-44D5-B127-B86C2C9C6877","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109f694e56b27f9cb4d5d136ff6e3720a6658764","datavalue":{"value":{"entity-type":"item","numeric-id":3740255,"id":"Q3740255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4161579c3c53be3a6ba9c59d582c9ece83670f03","datavalue":{"value":{"amount":"+0.8252277","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$FA128385-6DD6-4707-8DDF-88880C4AE951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1c81bf6dfc062bebabee9b36f1f45441b9b73cf","datavalue":{"value":{"entity-type":"item","numeric-id":3476627,"id":"Q3476627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"96cb274fc66e910c5d19b466eee25ec1539f7904","datavalue":{"value":{"amount":"+0.8231671","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$0F76A19B-0C91-4A06-8D3C-0CE4FF2BE18F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e18434d73da1c0497fb9d34753ed36e7f4532d23","datavalue":{"value":{"entity-type":"item","numeric-id":4305362,"id":"Q4305362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3526a255f581e6fd23c6189e5c6b14e68fd93996","datavalue":{"value":{"amount":"+0.823095","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1111019$0191741B-D91D-4C77-8FF9-200D709ACC6F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Min Cut is NP-complete for edge weighted trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Min_Cut_is_NP-complete_for_edge_weighted_trees"}}}}}