{"entities":{"Q3525616":{"pageid":5555520,"ns":120,"title":"Item:Q3525616","lastrevid":50457746,"modified":"2026-01-14T02:39:02Z","type":"item","id":"Q3525616","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 5344703"}},"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":"Q3525616$E521C0EC-6DF2-43D0-9E7A-90A882CE7B79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8041bb1ca3f3468ec1f4d81742c9073c4794f48e","datavalue":{"value":{"text":"Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3525616$1F924DB1-5B62-40F5-9829-79976E28BAEB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"22ff7ca1534b0eb2e3c75e67be9ccab1133d7a7c","datavalue":{"value":"1147.68529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$FBD0FB03-E285-4718-A001-2FE659E0C184","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"44be4974894ba273fe3be88cdf2dcee70ccca308","datavalue":{"value":"10.1007/978-3-540-74456-6_65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$E0F72BF1-95F2-4968-8A1F-80D362D67AE7","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":"Q3525616$EE0A7980-21C9-40D3-8A2B-CA26F2668416","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":"Q3525616$26FE7342-3CEB-4D51-B281-6BE72AB197B7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1ff83169d82e0f9719f7f3621056cd8c6ecbd125","datavalue":{"value":{"entity-type":"item","numeric-id":3525549,"id":"Q3525549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3525616$A5A1E786-A60B-4D16-82DC-3B7DC77E1ED3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c7c6c778a05329d7667480e28a68302bbad05fa7","datavalue":{"value":{"time":"+2008-09-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3525616$ED5B166D-BF0E-439E-88AE-377DC3BB8CCC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"65c64c6fb34c460df04ef1f1f400e87b03cf98b6","datavalue":{"value":"https://depositonce.tu-berlin.de/handle/11303/15620","type":"string"},"datatype":"url"},"type":"statement","id":"Q3525616$28611191-AEC9-4571-B601-9DD042FB0F7D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$9731CED5-38A9-493C-8BB6-0E7A4060B4FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$533F131E-6B29-4940-B2EB-8D8E8D2C4E01","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f6bf3893d629e887e64fe0347847023c0bf3145","datavalue":{"value":"5344703","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$9D7D2569-2DA4-4AA1-B832-F9E5339B2C04","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"286099febd7897a1c26d8bc07cb5c0a20074804e","datavalue":{"value":"vertex-recolouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q3525616$B164F2E9-DF05-4F23-8A60-6B5E82FD9F4A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"26da22ac57b0977c27e75bc0b973808b52895731","datavalue":{"value":"colour graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q3525616$DB62B889-A006-4E77-814A-5DEECE9BFDBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q3525616$79641D08-D7A2-4090-AB0F-474136FEADD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee8fa91a149e2b7419affe432673bea3b3d4ac01","datavalue":{"value":"superpolynomial distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q3525616$7C6A3E6C-E054-4BB6-858C-B14A803A299A","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":"Q3525616$63792867-DD8D-4620-81DA-AACDA1333105","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"508b3608fa2b6cd692a98b4d494de4cc0d39830d","datavalue":{"value":"W4237942241","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3525616$1A30EFD1-CABE-419D-88A2-6396FFF6563C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"27b28c49373f56badd717a578b1fa90c6ea52f84","datavalue":{"value":{"entity-type":"item","numeric-id":1034528,"id":"Q1034528"},"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":"Q3525616$08659ABB-30C2-4FD2-B8E5-83878CFAB81D","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":"eaf542d3d91300d369cdfbbe7df6251e544027af","datavalue":{"value":{"amount":"+0.9289969801902772","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":"Q3525616$07B7E172-B6F8-4A33-808A-5B24C6F9CABD","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":"a9b411dd773da7ee68444e27935a35b8d9e4d5cc","datavalue":{"value":{"amount":"+0.8488427400588989","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":"Q3525616$445CBB84-999F-4652-AC12-4445A72CCECF","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":"24246ac25a105425e3e165427fdeed1fc258e877","datavalue":{"value":{"amount":"+0.84563809633255","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":"Q3525616$66E81352-204E-462C-A068-BEDF09FA7B2C","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":"4687111251f8bd84950cca422f5b74b2e197e0ee","datavalue":{"value":{"amount":"+0.8342703580856323","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":"Q3525616$4AF4DA77-375E-4AB9-BDAE-9996460461BE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3525616","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3525616"}}}}}