{"entities":{"Q593988":{"pageid":595764,"ns":120,"title":"Item:Q593988","lastrevid":62990778,"modified":"2026-04-11T09:32:53Z","type":"item","id":"Q593988","labels":{"en":{"language":"en","value":"The max-cut problem on graphs not contractible to \\(K_ 5\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3833729"}},"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":"Q593988$66C9E15D-6522-44AF-B7CD-B69E11F3A732","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ab1a1be93956c0a3f1923c9a1e3e6dc4bb772c8","datavalue":{"value":{"text":"The max-cut problem on graphs not contractible to \\(K_ 5\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q593988$5CC429C4-9F93-4702-B566-0A06690EA1AE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a959657b7a2ac0f0a773686311d120c577411b9","datavalue":{"value":"0525.90094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$72B2AD60-EC9A-41BC-8590-3522D4E10860","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36a03c361e6f4b94cbe4c3eef2b6c77da4cb20db","datavalue":{"value":"10.1016/0167-6377(83)90016-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$EFD65011-FF59-4055-8530-F55C5604579B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"65634c2d7f7dfc4f36bec0cd396792e04d171618","datavalue":{"value":{"entity-type":"item","numeric-id":270026,"id":"Q270026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$408B490B-72C3-4206-8EA1-2AE664746659","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f9747a37b0b56aeca2085282046e2737cd5087ca","datavalue":{"value":{"entity-type":"item","numeric-id":96289,"id":"Q96289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$67FF8471-4E47-486E-96FF-01295F0B1CE2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0136733d5dd7d9f4d36f24c87a0b8375ae1cb2fd","datavalue":{"value":{"time":"+1983-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":"Q593988$DF314358-64DF-4243-ABBA-26CE494C90D7","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d2d4f4e28fa9ca38421c473fcb6ba728a44de59a","datavalue":{"value":"90C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$39D528B5-EDB8-437F-9294-DD301D2A6451","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"3feee98fb6a1a95642ba0c6a16390527874922bf","datavalue":{"value":"90C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$2835CBA8-8BB5-4518-A14B-A59191AD8A4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$E2551B8F-A928-4B1C-BEA4-3D37259BFC60","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d96a6e000eece3c48201a9c0bd1847e572c60898","datavalue":{"value":"3833729","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$AD84095B-089B-4C8B-AEB4-37BAF671DAD9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$DF989F1C-F4EF-4274-B14A-91256BB3C054","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b5bb75cfd9388347bbc3b89767c50d4269043a4","datavalue":{"value":"polyhedron of cuts","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$26DA2417-41A7-4720-B0A2-E2F15EF2A0FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fc544e482aa599702c82d69a25709014b297742d","datavalue":{"value":"polynomial algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$A49F8472-BFB4-4CB6-950E-AB925ECBE2BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d665173dc81790294af37e94b0e9f3bf8df667fc","datavalue":{"value":"max-cut problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$68FE0ED2-059A-40F6-AA8A-B6055D64CC7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$2365692C-C5F3-4053-B082-19AC2DE5802F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"599981ae0f13000555cdfbe3e563d6ac043c85d5","datavalue":{"value":"ellipsoid method","type":"string"},"datatype":"string"},"type":"statement","id":"Q593988$6456EBE2-B9FB-4B75-A486-DB99350543E6","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":"Q593988$B5285149-7057-4DA2-89DC-749D2BA90FDB","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ea67ffcadad77ed42346ba0f3e8285f0525cea13","datavalue":{"value":"https://doi.org/10.1016/0167-6377(83)90016-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q593988$5B75B1F2-A5A9-44B0-8F77-FD35774CEF90","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a1eb6899b356fa4a7ebd90b39baf918ab71908f3","datavalue":{"value":"W2060660073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q593988$1A531074-9C02-4221-8D8F-AE16311BF338","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a20078628f794ddae46e4d65dc4a9be93052fb8b","datavalue":{"value":{"entity-type":"item","numeric-id":3039038,"id":"Q3039038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$ED51D050-AE21-45F5-B525-21C251E6B178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8fa3587292ce5200d2d2f9d3d9e3d750b101421","datavalue":{"value":{"entity-type":"item","numeric-id":3939599,"id":"Q3939599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$FB661D56-206A-4495-9295-93E8E266E5C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"273bb8be43b497baa3a710fb525da21d668a4d19","datavalue":{"value":{"entity-type":"item","numeric-id":3699730,"id":"Q3699730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$85798D6C-0E4C-467A-8EFB-CA8951C7ACD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7c211e55116d68a1af38ddb2786888a3b5b61452","datavalue":{"value":{"entity-type":"item","numeric-id":3773723,"id":"Q3773723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$88CC3A8D-6A2C-4DFE-AFFC-A97BBDC83DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7bd8b848f40aaa3f56b8b15df38fbe662aeb1afa","datavalue":{"value":{"entity-type":"item","numeric-id":5516087,"id":"Q5516087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$108B82A3-5ACA-4864-8763-2F1A93E36812","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":"Q593988$63562864-CC64-450B-9A42-EC24924DCD07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e34bc8de7dff9e6ae38acf775674b87311a55dc0","datavalue":{"value":{"entity-type":"item","numeric-id":1169411,"id":"Q1169411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$D07F774A-8F52-41A3-A36A-79166EBC863A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad0ccf7c915e555b736052d9a389d9d40d6ea980","datavalue":{"value":{"entity-type":"item","numeric-id":3315282,"id":"Q3315282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$0CDF5203-D07D-474C-894E-8B3ED3B6F807","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ca8e2226bc49403f5d34bedd57297744e386790","datavalue":{"value":{"entity-type":"item","numeric-id":1168215,"id":"Q1168215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$E0FB3E4E-DEC5-44E7-8C8C-3C05F5374AA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849849a8734e624cdd488bd27603bced49d0bfd9","datavalue":{"value":{"entity-type":"item","numeric-id":4083698,"id":"Q4083698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$66AC8EA3-E48F-4453-ABBE-53187E75BC1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ff469158b0917cd489eec9d6ddfd641a6e6e677","datavalue":{"value":{"entity-type":"item","numeric-id":5659589,"id":"Q5659589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$D8CF0202-82E0-4CA2-B7EB-9FA871870340","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4fa5c0efe0c39997534bb44636c6730a4e42c655","datavalue":{"value":{"entity-type":"item","numeric-id":3965907,"id":"Q3965907"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$347F4207-A93B-4414-A5AA-5408BB727701","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1c30f625799516073453005ce767ea0c97beb0a","datavalue":{"value":{"entity-type":"item","numeric-id":1157338,"id":"Q1157338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$2CE46AC0-1160-487C-9A8F-D16062C37391","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"451cbb39afc126b40f7b3c239c65e065b043391a","datavalue":{"value":{"entity-type":"item","numeric-id":2538210,"id":"Q2538210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$B3C053AF-6EDC-44D0-BE04-E1F0149B594E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c0220f1b47cc11d07d957e8fdb5cbc82997f8899","datavalue":{"value":{"entity-type":"item","numeric-id":5592127,"id":"Q5592127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$99B8105B-3CD8-41B6-B092-0618B2ECDE5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53931acda4d1de6fffc8c785b472a64b77dbbda9","datavalue":{"value":{"entity-type":"item","numeric-id":5402565,"id":"Q5402565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q593988$543A96AF-B195-47CE-BB94-3598F8F84612","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"The max-cut problem on graphs not contractible to \\(K 5\\)","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/The_max-cut_problem_on_graphs_not_contractible_to_%5C(K_5%5C)"}}}}}