{"entities":{"Q6047965":{"pageid":13182121,"ns":120,"title":"Item:Q6047965","lastrevid":58652802,"modified":"2026-04-06T04:49:01Z","type":"item","id":"Q6047965","labels":{"en":{"language":"en","value":"MaxCut on permutation graphs is NP\u2010complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7747704"}},"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":"Q6047965$BCE977F8-D09B-486D-B066-B75BC8769640","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"35620a589adfb27bbb7b1b23a14b9f6f1322e667","datavalue":{"value":{"text":"MaxCut on permutation graphs is NP\u2010complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q6047965$92E5F6AC-BFC9-4FD1-9484-E8FDC823DE4C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8194275e4297e0d41e3cff3373ee47d709a37375","datavalue":{"value":{"entity-type":"item","numeric-id":1567274,"id":"Q1567274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$1DBAEDFD-010D-4F27-96DD-107BB437081E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fadb8dcb98135447429e044e4390039b25d104aa","datavalue":{"value":{"entity-type":"item","numeric-id":831819,"id":"Q831819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$ACCE0F62-49CB-4510-92B0-40CF8462B7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"517c752f52a7041d67efeb30674a9c5a491c5025","datavalue":{"value":{"entity-type":"item","numeric-id":831862,"id":"Q831862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$8FBC9876-1539-4EE0-9A5B-0C345E63B3FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4970e686d0aeed49a73cc5175bf2484129cef55e","datavalue":{"value":{"entity-type":"item","numeric-id":6047964,"id":"Q6047964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$1CE99160-A175-45E7-AED2-E1149BE2061C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"4de5c7a5d238217ab4a071d198b3a40ee05be465","datavalue":{"value":{"entity-type":"item","numeric-id":2725046,"id":"Q2725046"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$4E668AB7-383F-469B-BEF4-C77DA635581B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1daaf5422e1249755fe6af9bf2de938be8d95b44","datavalue":{"value":{"time":"+2023-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":"Q6047965$2EB42F77-30D9-4D1C-94A1-64C5ACB24EC8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fdbf45cd6cc33b27d3a6fe075284b2b79ebfdc28","datavalue":{"value":"https://arxiv.org/abs/2202.13955","type":"string"},"datatype":"url"},"type":"statement","id":"Q6047965$8C945097-AB2C-429D-8562-BC5077097858","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6047965$D50D7DE8-C2A2-47E9-805D-ADCF887EEDF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6047965$926DBC15-3A81-4E26-A226-13394E659F30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6047965$708C1B74-B6FB-4E41-8F35-904D248D04EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f0777d65a4b6cefa000b92a7ab7ebc7de3a979bc","datavalue":{"value":"7747704","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6047965$3001A273-F324-4BF5-9FE0-A6CFAA7FAD3F","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2ba0cc3f7aaac8445724ef309c9eecb57f5a563d","datavalue":{"value":"computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q6047965$76AD13C7-6D9B-48B0-A93B-B85724D2C4A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2fd54d79f35d0438b5b6e2624ac5e2d582d6e321","datavalue":{"value":"maximum cut","type":"string"},"datatype":"string"},"type":"statement","id":"Q6047965$98551558-E67B-45EF-8623-2AE6A22D0A2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f5498ca3e7abb035a7212a6e68902ac2f3c0126","datavalue":{"value":"NP-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q6047965$3CA19BB3-6595-4FF4-BED7-58CE43C33C7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972b47051b12a25f42ccd0a9702464009e0dcd44","datavalue":{"value":"permutation graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q6047965$87633396-AB1D-43DB-BA7B-982B90F396F5","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":"Q6047965$366B7CB3-6FF0-402D-99C2-5176B84BA04B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"163d82d11dc2551a2363687649bb065e3c157503","datavalue":{"value":{"entity-type":"item","numeric-id":6174803,"id":"Q6174803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$165CA822-4ECC-4DFC-955C-CE7C576AF5E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d51de4e740e798482befadbd50fb363b61fd9fa3","datavalue":{"value":{"entity-type":"item","numeric-id":4942616,"id":"Q4942616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$D917246E-7292-4892-99BE-E73599E8E5FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$E97568A1-BF82-4D7F-A487-6D0643B35FAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"92beca96c1600cba1ea40ade0777b7e7af5718be","datavalue":{"value":{"entity-type":"item","numeric-id":2091799,"id":"Q2091799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$4020B512-368F-423C-AD23-C88948858A88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bf41eb9a7cdecfa7d656e1a023eae669e315011","datavalue":{"value":{"entity-type":"item","numeric-id":6168453,"id":"Q6168453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$89913617-BBD6-49C7-A114-CDE94B0FAB28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bce677a9c061b16210c3b75fe5d9808dd9ed326","datavalue":{"value":{"entity-type":"item","numeric-id":1060230,"id":"Q1060230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$DE3208A6-8182-4C7E-A1D2-ADB7A841B492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$DE7D92B5-2B61-485B-9F50-FCC1C76F1E2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$46BCBD77-994D-4B97-A88B-7990C05986DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c17b1143dff0bc685088f8d62dbc046a1f96e02e","datavalue":{"value":{"entity-type":"item","numeric-id":5732670,"id":"Q5732670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$16788D5F-AA48-4A45-9A4C-FD92D77E7C1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3b07b5dcf0b43c9f49e2d29db88bee73b1cb11be","datavalue":{"value":{"entity-type":"item","numeric-id":1886097,"id":"Q1886097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$07C6EAFE-666E-4B9E-9001-59C5278A3B30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db0285625f074a48cd1908122f2f7d851fdd299e","datavalue":{"value":{"entity-type":"item","numeric-id":3747723,"id":"Q3747723"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$E26621A2-CF98-4DAA-BAB8-A7B7343A4E92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3cd900a9928338cdadd8e18c47b33b430f9560c7","datavalue":{"value":{"entity-type":"item","numeric-id":5602691,"id":"Q5602691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$9DFFB1CB-7A95-4F79-9AB0-0BEC0B65CB2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"69f254905ff1ada4c9ba698b1b0da28d301a3fb7","datavalue":{"value":{"entity-type":"item","numeric-id":1396949,"id":"Q1396949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q6047965$6B415651-3FC3-46E4-8D30-D79D3EA374AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a2ceaee114be522f20e5025f8f1af05d9d7f610","datavalue":{"value":"10.1002/JGT.22948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q6047965$BE88765D-AAE1-4802-882C-2E401AD3DB62","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:6047965","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:6047965"}}}}}