{"entities":{"Q5075794":{"pageid":7105370,"ns":120,"title":"Item:Q5075794","lastrevid":55409623,"modified":"2026-02-17T15:49:00Z","type":"item","id":"Q5075794","labels":{"en":{"language":"en","value":"On the Hardness and Inapproximability of Recognizing Wheeler Graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7525488"}},"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":"Q5075794$603A5EE0-F4DE-4288-BEDC-42343B13D5B4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bca5d2e1483a781057b81aeeb549f042c3077a85","datavalue":{"value":{"entity-type":"item","numeric-id":2118210,"id":"Q2118210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$D311F904-20EE-4C35-8AE3-0BC11675B0DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0d1afd926af2da6a4211f7ba4ded55381c3500e6","datavalue":{"value":{"entity-type":"item","numeric-id":261368,"id":"Q261368"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$F43DAEDC-D700-4473-8535-BD1CE964D6F0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"33eb095e7a11594535a14f244480079f6a32a297","datavalue":{"value":{"time":"+2022-05-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5075794$893DFF13-DA5B-4191-BE01-E379977BBDE0","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"94a4638ee6124e95c4262c9dbd1bf1b3fd2cfd29","datavalue":{"value":"https://arxiv.org/abs/1902.01960","type":"string"},"datatype":"url"},"type":"statement","id":"Q5075794$85056045-113E-42D6-B78F-CE8FAB6F9D13","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fa684c8d52e9da1094b0c2d762898ace723c7ee3","datavalue":{"value":"68Wxx","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075794$22900BDA-1965-454F-BB4F-61BD44A253DF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d5a5bf2bce1959214bfbb446b4fdf5e23402c662","datavalue":{"value":"7525488","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075794$8680A1E4-D24F-4FAD-BB64-C83A60BA3267","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3e7a436225d167e640e175e5d4534bbc928fa3a","datavalue":{"value":"Burrows-Wheeler transform","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075794$1659B9FF-11D0-4B73-ADCD-FF0E9F4FEB38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfe87d9c5acf813f3aee69660faa8f65c2998584","datavalue":{"value":"string algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075794$FA9F5898-E538-432C-90BC-64BD64A596E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5ee40f8f543659211b421d3bc4734492ddad5ca","datavalue":{"value":"suffix trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075794$2C5D24DB-7CBF-4E1D-A939-3320D609EA58","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cf1bbad404b660dcc4f7e1f74269a25b269f6b2f","datavalue":{"value":"NP-completeness","type":"string"},"datatype":"string"},"type":"statement","id":"Q5075794$1B5DFDB8-64A0-4D48-87F6-FF6B232372C1","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":"Q5075794$63255B31-F83D-4811-8FE7-1F5664D0F814","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e884892508373839ae801c95d241a499a8aaf0a5","datavalue":{"value":{"entity-type":"item","numeric-id":4055184,"id":"Q4055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$6C9A1DB5-3F88-468D-9D2A-8AFFE499456E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aff148122a0178311a656417a4021b222d247a5a","datavalue":{"value":{"entity-type":"item","numeric-id":5146826,"id":"Q5146826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$C3E20BFB-D710-4F4E-B2FA-CB9BC67B649A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e95e30fd327c54b08959dfb9a3c7f39de15a058b","datavalue":{"value":{"entity-type":"item","numeric-id":3575239,"id":"Q3575239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$FBBCE78E-D4F7-488B-9871-84908661D579","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c533316b774870b20c80bf8d0dd942a75a387698","datavalue":{"value":{"entity-type":"item","numeric-id":4916912,"id":"Q4916912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$7B2014AB-4DD3-42A2-9CDB-4A43AED421AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7d2a6eecb3b45c6b8c76ba90d659344414c0fdc3","datavalue":{"value":{"entity-type":"item","numeric-id":3452187,"id":"Q3452187"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$CDA46C13-4931-4560-A57F-9F04D1214477","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a350a646df05af2cd765c289d28ce10d45e83b7d","datavalue":{"value":{"entity-type":"item","numeric-id":5834367,"id":"Q5834367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$5E8E1233-796F-4B53-B107-7920B6A5E0EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c8f519ca2c24d87effaeaffe2a823e1425495c1","datavalue":{"value":{"entity-type":"item","numeric-id":4667610,"id":"Q4667610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$61DA7C67-B0FE-4D29-933B-5B631F76C97A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"44bb59cdd9c3ea06211f52ececeacdf11770c2aa","datavalue":{"value":{"entity-type":"item","numeric-id":3455566,"id":"Q3455566"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$271CC214-692F-44C9-8A2C-D999AF9DD76C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f1ef0c6008067a98e6eb681185db01b14f722a","datavalue":{"value":{"entity-type":"item","numeric-id":3546296,"id":"Q3546296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$1218BBCF-F6FC-47A3-87CE-6A821BD002BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"075c711e2f2721653700f6d4fbb5157eecbfe946","datavalue":{"value":{"entity-type":"item","numeric-id":3188992,"id":"Q3188992"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$8EE04F53-6311-4340-B38D-2F0BE77B18FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c3749d7b0a0615b6cbbb5620bae59c9d84abe0cf","datavalue":{"value":{"entity-type":"item","numeric-id":1676308,"id":"Q1676308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$DB599744-6A1B-4145-9A60-BBE1C3C9C04F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef70f70dafaec68595f39cdb8cc0ebba50cd6b78","datavalue":{"value":{"entity-type":"item","numeric-id":4575762,"id":"Q4575762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$13FB5181-5E68-40D9-BC7F-38F0D37628C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f842ad3f349f8e3a5080defcf4e31ea1a2db15eb","datavalue":{"value":{"entity-type":"item","numeric-id":2118211,"id":"Q2118211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$47DEB065-D7F7-42D8-988B-65C97A60BDC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88aa0fce0552ef17a141f1cdf7233250eb6f2665","datavalue":{"value":{"entity-type":"item","numeric-id":4268810,"id":"Q4268810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$6073F0AA-C168-4125-B3FB-1471E2F116F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"30cfad513dc88eefe9763658d40f664012105fa9","datavalue":{"value":{"entity-type":"item","numeric-id":4268720,"id":"Q4268720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$F670F57E-57B7-45EF-8CF6-0C1361C9CB3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ff436a1943b4ea6694b9f55741c91c233d4cf66","datavalue":{"value":{"entity-type":"item","numeric-id":4015976,"id":"Q4015976"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$8220269D-7BD1-4645-9FCC-146390E97D03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37596501a1ce03ff93efb58b06bfc3f66aa2a4bd","datavalue":{"value":{"entity-type":"item","numeric-id":1939285,"id":"Q1939285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$3AC3605E-E48A-4A8F-B570-F24A4D619B9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"56d82821881f760c9d448de886ce17451073ecf6","datavalue":{"value":{"entity-type":"item","numeric-id":3569014,"id":"Q3569014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$AB41E4E6-0392-4214-AA2A-789D50E6B6A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba7aaf40d98e19a1799d4692b8b37253f3b9a80a","datavalue":{"value":{"entity-type":"item","numeric-id":2465062,"id":"Q2465062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$85FB1989-EDE5-4DB8-A619-63C3C7232327","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"811d62b45a33ee04d067b49bec2d40ea70684bb0","datavalue":{"value":{"entity-type":"item","numeric-id":1255944,"id":"Q1255944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$F2ABED06-CDFB-44E3-914E-96EFC35BEE29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36668365b781aef3815bad53aed4aa2e26c1fade","datavalue":{"value":{"entity-type":"item","numeric-id":1706509,"id":"Q1706509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$33531F3D-5899-414A-A116-279FB328BCEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a78f9085e5e7b89758d1047fa19fb1d1eff42fe2","datavalue":{"value":{"entity-type":"item","numeric-id":4178507,"id":"Q4178507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5075794$E9AF1F6C-3EC2-4296-B2A1-504F1D5898D5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"169e9a7622252d988af001cb8e59131a8641d473","datavalue":{"value":"W2977558816","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075794$8105C490-5470-4F1E-BD89-CF091456CBF9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"048dd7ddf4324ff537fcb6e0da57f166f3886026","datavalue":{"value":{"text":"On the Hardness and Inapproximability of Recognizing Wheeler Graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5075794$7162C4DD-15A8-4421-97F1-39B07C580809","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"adbc24000581d5f30c786d33a8942b12ac6afaff","datavalue":{"value":"10.4230/LIPICS.ESA.2019.51","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5075794$9AF101BC-1F02-47BC-B6E2-B47D1FC346CF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41cc9f9b894c274daab581e327a4370f972fd98f","datavalue":{"value":{"entity-type":"item","numeric-id":2118211,"id":"Q2118211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a47f91a3f46e3ba9b0ef0b1ddf26eee135bfaaf","datavalue":{"value":{"amount":"+0.9922984838485718","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":"Q5075794$2993DDC5-3C91-47D2-930E-9336AD107CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7770ef3220f68434abc8a19047a99e52bea168b0","datavalue":{"value":{"entity-type":"item","numeric-id":2051845,"id":"Q2051845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"029e47adca57475a5dd50368d6c76d129e3060a8","datavalue":{"value":{"amount":"+0.8131853342056274","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":"Q5075794$02E1EAB2-0F50-4356-9D08-D485ED44FCDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"632f65ceb27b9cbd6ef655ac7dd96a6e2378bd42","datavalue":{"value":{"entity-type":"item","numeric-id":1676308,"id":"Q1676308"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"52ac7b5654c02ea956bd78aeaaa40de66adfac31","datavalue":{"value":{"amount":"+0.8060938715934753","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":"Q5075794$48B9FAA7-42F9-4205-9AE9-CD18A24A0293","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ae7c590014727219061ade7fd420b652b9893c58","datavalue":{"value":{"entity-type":"item","numeric-id":6545413,"id":"Q6545413"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"168dd71290ae396d350f7b5bd1426f883e3ac481","datavalue":{"value":{"amount":"+0.7981220483779907","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":"Q5075794$D9B618FA-B44B-4E61-938B-F80B6D5FB61A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c952336b02e6f86b9ef1a72fd658a95757a2113","datavalue":{"value":{"entity-type":"item","numeric-id":6103519,"id":"Q6103519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a0e937c4c8b7036f388fe58f9f27841561a4237","datavalue":{"value":{"amount":"+0.7895873785018921","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":"Q5075794$ADCB1125-708B-4123-9085-30C82D91A983","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5075794","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5075794"}}}}}