{"entities":{"Q1034528":{"pageid":1036376,"ns":120,"title":"Item:Q1034528","lastrevid":69472434,"modified":"2026-04-13T07:14:12Z","type":"item","id":"Q1034528","labels":{"en":{"language":"en","value":"Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5626889"}},"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":"Q1034528$CA5F3C05-750D-4BC5-B57D-E5BACDF06C31","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f6cbea2c1567bb638b67a6482fda81791de32c6","datavalue":{"value":{"text":"Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1034528$C6A107C8-32C4-4BDE-B7D0-D780661610AC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cf3b7ccdc1a9f3bd11ae1c963675ce5d43367286","datavalue":{"value":"1177.05112","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$DAAEDB6E-CD4E-400A-965D-3F1679937B86","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"54aef55090a96c8e785afe18ef049813d4edd9d7","datavalue":{"value":{"entity-type":"item","numeric-id":392172,"id":"Q392172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$F305BF0C-F5D8-4D93-AE1D-78D5F9E1FF68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"531ebdfa676a3c20cc9550c6f43f2c523217efcd","datavalue":{"value":{"entity-type":"item","numeric-id":1034527,"id":"Q1034527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$580E1038-76D5-463B-947B-C57D3AF0C0BF","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":"Q1034528$9E3B9199-E94E-457B-9070-8FD65FFE8057","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5c80b38051786df2940873db0a591fda80f5fbfc","datavalue":{"value":{"time":"+2009-11-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1034528$AF33714B-46FB-412E-B5CA-43D86A0F7287","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$E15810D7-9C95-43CC-A42A-C29417A72359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$47CDD479-B969-4F91-AC38-0512EE71A329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$7A8D2C84-A095-401C-9B22-32D4CEC58EC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$A108EAC3-1E73-49B7-BEAE-870E2382D7D7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d984f09f98aeb8bce6ee88586a5405a8908bcc2d","datavalue":{"value":"5626889","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$792E5DE9-0F91-4612-9B32-5B2B7817A84A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"286099febd7897a1c26d8bc07cb5c0a20074804e","datavalue":{"value":"vertex-recolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034528$E9FD1B8A-D068-4E06-B427-6BB3AD732711","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26da22ac57b0977c27e75bc0b973808b52895731","datavalue":{"value":"colour graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034528$D94A1073-DC44-42A9-9FDF-EF4301170A7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034528$EF00B2B5-1E4A-46BD-ADFA-9DF30650A36B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee8fa91a149e2b7419affe432673bea3b3d4ac01","datavalue":{"value":"superpolynomial distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1034528$55A3D619-37C3-45FC-86AE-8F6372CDEEC9","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":"Q1034528$BA8E4252-EB65-414F-A5C9-E424FBF0ED6C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"86093ec3b68383a08a6f7091d7e4c7bcf28c6ae0","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2009.08.023","type":"string"},"datatype":"url"},"type":"statement","id":"Q1034528$BF80F120-5DA8-4FF8-8183-0A61F8E62999","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3801c56b3c5ea9a31a4967f37fd3d7995bc9bf0c","datavalue":{"value":"W2036323482","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$B5C18153-8BD2-4710-BB51-0208B5D2A4D0","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e070597e4e72e0ddfb8bf1003bf1873c1c51c13","datavalue":{"value":{"entity-type":"item","numeric-id":2470462,"id":"Q2470462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$19068438-E0E3-4926-A755-37E083255766","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"946774547220fd5380b84eea93668f5e93e756b6","datavalue":{"value":{"entity-type":"item","numeric-id":3508565,"id":"Q3508565"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$2ADD0DD2-34C3-44BD-8560-C43BDFCC64FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd93d3d977e123e0f2949cd69e65d6763732c40a","datavalue":{"value":{"entity-type":"item","numeric-id":3104271,"id":"Q3104271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$2930AC98-4501-4C5E-B4A5-182BA53490AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a998553d04d92ec750c5db95c511cc38b8ab7659","datavalue":{"value":{"entity-type":"item","numeric-id":5315023,"id":"Q5315023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$9703EB38-65B5-4442-935A-BB90F212E57C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4aaf62d8b0dd458e9bc5f818a51a609edac9992f","datavalue":{"value":{"entity-type":"item","numeric-id":3419603,"id":"Q3419603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$442F9396-9AF9-4A60-BC1C-18539B925935","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":"Q1034528$968B8D5D-5B4F-4F0A-86EB-1313941BEDD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a68b8d005dfd87902f37fb8cb4e60330d36c756a","datavalue":{"value":{"entity-type":"item","numeric-id":5902502,"id":"Q5902502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$FFCBD5A2-31D8-44BC-B578-40D83364F694","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e184195c5a8284dcbf17831e106578831ea79773","datavalue":{"value":{"entity-type":"item","numeric-id":2570127,"id":"Q2570127"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$E77D4D9B-FBE0-4CBF-A7C9-FC047E59E0EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c3eb320d4b98114e1bab22bcaf8058810629bf3","datavalue":{"value":{"entity-type":"item","numeric-id":4798347,"id":"Q4798347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$4C0C6425-BB5A-4B8C-95DE-ABDE2BD79881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$8D42E748-13C9-4860-8551-537B6CEB69D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1034528$815C142D-C736-4FE0-A81B-20C1BF7464F7","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b1240a8c8262856fbc15963e640948979f781f04","datavalue":{"value":"10.1016/J.TCS.2009.08.023","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1034528$90DAF595-8222-4844-9D9F-1B547A2D9B59","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71f56e5a89f7926a11a4126948a886d5d83b2b1d","datavalue":{"value":{"entity-type":"item","numeric-id":3525616,"id":"Q3525616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"20a975ab67c6da5854623983a6182ab73301e95c","datavalue":{"value":{"amount":"+0.9949854016304016","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":"Q1034528$4BB300A6-6150-470A-B6C9-0F47C40ADEE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d96eaa5fe7d12bc3bc98f05d9f32e101c342ed27","datavalue":{"value":{"entity-type":"item","numeric-id":3503504,"id":"Q3503504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a642c75a6201c236f04d281171e333fd389aae6","datavalue":{"value":{"amount":"+0.912821650505066","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":"Q1034528$3581896E-E68A-4A18-A817-F7A27F2D8A9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6fe6b532561eb6a40eb31344fdfadca20269b0e","datavalue":{"value":{"entity-type":"item","numeric-id":3104271,"id":"Q3104271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a7a78b2ed2f53c044119931961ad833fffef7c6","datavalue":{"value":{"amount":"+0.8353508710861206","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":"Q1034528$3CE9B07E-2438-4633-9DE4-6158B882D18C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a51a146b5446033920395d20cf5d57f9317676cc","datavalue":{"value":{"entity-type":"item","numeric-id":1699776,"id":"Q1699776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fb9e4e4c243cb8a44b05c505abcb0cb2aebebba3","datavalue":{"value":{"amount":"+0.8318099975585938","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":"Q1034528$DF13B60F-22F4-4C51-B21B-7146F2475D52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f3fdcf42ff8bc239ffcfcbed158dc4af4e598bc","datavalue":{"value":{"entity-type":"item","numeric-id":2998926,"id":"Q2998926"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"505a1c80b7a9edb30880098219ff70092c38ecdc","datavalue":{"value":{"amount":"+0.8315422534942627","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":"Q1034528$D3E56525-6B79-4850-9D41-9208BD46BF4D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finding_paths_between_graph_colourings:_PSPACE-completeness_and_superpolynomial_distances"}}}}}