{"entities":{"Q893321":{"pageid":895169,"ns":120,"title":"Item:Q893321","lastrevid":65146749,"modified":"2026-04-12T00:37:59Z","type":"item","id":"Q893321","labels":{"en":{"language":"en","value":"Computing the greedy spanner in linear space"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6511729"}},"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":"Q893321$888EA504-8F38-47B7-B3FF-54B867C5739E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"371503433418ca9a6fb28c6d984e49893d7374b9","datavalue":{"value":{"text":"Computing the greedy spanner in linear space","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q893321$A9C5039F-5149-497D-AFFF-F7D206A6C8C9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7b72d7ab2ee27a2df784be05fc05cd672410e3ee","datavalue":{"value":"1325.68245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$E3DBC453-5781-43AB-A8BE-5EEF13F69E62","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24d7a1f77268fd8a77404a1dd0c22d9e93318e57","datavalue":{"value":{"entity-type":"item","numeric-id":527419,"id":"Q527419"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$B22C0C5B-35FE-42D6-989D-F9ADA40127EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96c11402b785f3856af6ae599034c4e38c7a8141","datavalue":{"value":{"entity-type":"item","numeric-id":527420,"id":"Q527420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$F9487937-42CD-4566-B14A-6652CAC0AA46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08f879a7647d1cc8d1a15d96392d98b98236946c","datavalue":{"value":{"entity-type":"item","numeric-id":527421,"id":"Q527421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$C7232BA0-8AB8-4875-987F-8C2F3F4A3C2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3a5290663200c60e3d3c8b72caf993a37ac18a7","datavalue":{"value":{"entity-type":"item","numeric-id":312137,"id":"Q312137"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$1ED4A3FA-AD58-4EAC-ABDE-15DCDB9AE97A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$76F0A8F1-B55A-484D-A9F0-8AAF08936B38","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"390e76e3a1fc3fba4c5512200895e5fc04f72056","datavalue":{"value":{"time":"+2015-11-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q893321$3F674E5E-4B65-44F5-857C-5929ED62259A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"159426a5937e62cfbbcc198dd4848ab52d6e715e","datavalue":{"value":"68U05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$9BB20889-87C3-4200-93E8-0574EF070D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$254986B9-E7A1-46D3-9D9A-70B2907FCB9F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5fef1c794e06f30ced5e722cb581ebfb08b0a390","datavalue":{"value":"6511729","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$43B54100-6532-41D6-A45F-4965A56043BA","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"48091832e7e9c4044dd8118cb98a84f364323532","datavalue":{"value":"geometric spanner","type":"string"},"datatype":"string"},"type":"statement","id":"Q893321$A6CD07BD-3A51-4966-8EF3-E6FAFC9BBA70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ada8d30f2ef08fc8cb2c5d1f7da969abbc27918a","datavalue":{"value":"dilation","type":"string"},"datatype":"string"},"type":"statement","id":"Q893321$AFA933CB-8372-41DA-A8EB-3365CA6B1486","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34021ef787f4e28495d35f81de19ab2bcf2b70ec","datavalue":{"value":"stretch factor","type":"string"},"datatype":"string"},"type":"statement","id":"Q893321$E9FC4C95-7848-4D99-9724-FFBA18044E26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e1e7eb452ae4c92c43fa47bb0afb8177365a429","datavalue":{"value":"greedy algorithm","type":"string"},"datatype":"string"},"type":"statement","id":"Q893321$B1E2D9EC-30BC-4A47-95B2-0D923A9BFA8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q893321$B80AB917-2522-4526-9C4B-1D9B8231A0D5","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":"Q893321$98A2D4EA-FD6B-4BE2-8CC4-4EB0B516D518","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7176e4cffa2bb1c0c6aa470a008fd4036c81af4e","datavalue":{"value":"https://doi.org/10.1007/s00453-015-0001-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q893321$8B846F81-928D-4094-8F16-2DC9F12CF911","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ad0a778758203561ab97768208690b6de9f54c4c","datavalue":{"value":"W2126497992","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$6513912D-A084-4F15-BBED-86B7BD4B9FF3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c30052c44b8a69f47358183891e7a7906693f08b","datavalue":{"value":"Q59427635","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$B0111FFD-8066-4EBF-A7B5-97880C4CFCD6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1ed098e2e40c90e4c8ec45ae4966d5e5ccd854","datavalue":{"value":{"entity-type":"item","numeric-id":2921394,"id":"Q2921394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$88D6713E-8702-47AF-BD1A-8EDAC3C9EFDF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"720eabf6dacef1fb4983e3e488dd61435cc9dca0","datavalue":{"value":{"entity-type":"item","numeric-id":1957650,"id":"Q1957650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$872B2F50-B92B-4DC0-A4EF-0F6DB68534F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"29016e166e3c7384487d663b067e4d76c9614b1e","datavalue":{"value":{"entity-type":"item","numeric-id":4635523,"id":"Q4635523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$18C946BD-C999-4DDD-B346-9BDEB337F6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"440ba0d9dbee427a1b508f6b771488e2dd84f87d","datavalue":{"value":{"entity-type":"item","numeric-id":4369857,"id":"Q4369857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$BCE3B795-8B95-4A19-8ECC-B5589D086523","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1a7d12ad715ea384e4f5dfa32c3b1f65fa44d396","datavalue":{"value":{"entity-type":"item","numeric-id":1823959,"id":"Q1823959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$7C13533E-C48D-492C-8B44-4C2AC5AE52C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe5c59ba87e10b27f297438f3ff7ca7fb6e503d7","datavalue":{"value":{"entity-type":"item","numeric-id":5406195,"id":"Q5406195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$52F94E4E-7C6E-4AD1-BD83-19452CF2013A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"392e49d37d1fa60d0fe31724999f41e77d3ddbd1","datavalue":{"value":{"entity-type":"item","numeric-id":2921666,"id":"Q2921666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$A8C3FC1F-33A7-423B-BAAF-F772B9EDD0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7d15327ffd5879a5a790fc19f6d3a2491c6d397","datavalue":{"value":{"entity-type":"item","numeric-id":3802644,"id":"Q3802644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$3FC4D3E2-23D5-4995-B39C-985710DCAD7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be3c5a8818c4c46851df63da12a053a069982e14","datavalue":{"value":{"entity-type":"item","numeric-id":3445775,"id":"Q3445775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$5103BD13-30B7-4E4C-81C9-D95953FE8F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd94578b97c83ef7077e73a3f78c579ae10dd88b","datavalue":{"value":{"entity-type":"item","numeric-id":3826599,"id":"Q3826599"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$B68E0A87-CA6B-4B67-85B1-CE81C74A9026","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"7e08eab7727fa7428443df6436575858160dbfbc","datavalue":{"value":"journals/algorithmica/AlewijnseBBB15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$252D2366-A938-41F2-920F-9782BD97C7FF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"fb436df2d08d47c6e65ae1fe5c8da827916d5219","datavalue":{"value":"10.1007/S00453-015-0001-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q893321$34CDFC69-0479-4FEE-86E3-22E48427EB2A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a30da12071da98dd8905ea90f891f619805fb5a3","datavalue":{"value":{"entity-type":"item","numeric-id":2849294,"id":"Q2849294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f80e952e76cf88b477a1bc81f79f6cb1ac211c86","datavalue":{"value":{"amount":"+0.9970901012420654","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":"Q893321$17B20BB7-F159-4D62-AC52-CA7DCAF74710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d28562a4f4f298115e86dcf24bc5fb1d4a3fdcdd","datavalue":{"value":{"entity-type":"item","numeric-id":4635523,"id":"Q4635523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23314103f751f169a704cef759c66d0233a70234","datavalue":{"value":{"amount":"+0.9255248308181764","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":"Q893321$5760564F-4522-4F69-A546-E16042C9AF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"24bac44db3e0f18f8424a0dbee3aaf1057ea25ac","datavalue":{"value":{"entity-type":"item","numeric-id":2921394,"id":"Q2921394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c40780510b23f2e9dac6440d7c33ef800fed10f9","datavalue":{"value":{"amount":"+0.9111427068710328","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":"Q893321$CC116F02-FBA5-4D22-896D-031C775F7558","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"854bd756de2ee6910698fc65c68f27db5d34f98f","datavalue":{"value":{"entity-type":"item","numeric-id":527422,"id":"Q527422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"baaccd2d1f7a05182eceb2e1d5526078cb838a1d","datavalue":{"value":{"amount":"+0.9091771245002748","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":"Q893321$8666C8EB-DEF5-41B0-975C-E321CCC2F737","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa44dae5ceab63adb2e4287a2067304fdbb6f497","datavalue":{"value":{"entity-type":"item","numeric-id":1957650,"id":"Q1957650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2475de79fbc60fcd36929b81f778785c9d8fd690","datavalue":{"value":{"amount":"+0.9082379341125488","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":"Q893321$4A62E446-D1AA-499B-8CE1-88F9F7BACC93","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q893321$AF16E5F5-CD43-4A97-8FA3-8FE04985CBA6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing the greedy spanner in linear space","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_the_greedy_spanner_in_linear_space"}}}}}