{"entities":{"Q883232":{"pageid":885080,"ns":120,"title":"Item:Q883232","lastrevid":50109974,"modified":"2026-01-13T04:09:34Z","type":"item","id":"Q883232","labels":{"en":{"language":"en","value":"Approximate distance oracles for graphs with dense clusters"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5161067"}},"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":"Q883232$86A1DF24-1BA8-4B78-9231-99F507607B60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"44db977cdc6b0f2bc153dda0d4443de8803d2e50","datavalue":{"value":{"text":"Approximate distance oracles for graphs with dense clusters","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q883232$F056254D-F7B5-47E0-B380-8973D113927A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cc7c7303d6f57204b801a0052324d9044982133a","datavalue":{"value":"1144.65010","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q883232$7F688843-2D4C-4E4B-BA03-1B409AE5B8DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2c471a57fa54a37409cb42578f114743a97980b4","datavalue":{"value":{"entity-type":"item","numeric-id":705544,"id":"Q705544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$3FBF30ED-B93A-4E03-BCAC-492752BC3D54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"08d599b23f730c4d985d728bd093d3200c3047b9","datavalue":{"value":{"entity-type":"item","numeric-id":391226,"id":"Q391226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$BBEF8A7B-1463-4311-A438-797FF9429B06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0dc835d004d9da5bffbf23ad19f48702adc4590","datavalue":{"value":{"entity-type":"item","numeric-id":582112,"id":"Q582112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$D2AC9A23-CE5D-449C-9705-04AF0AECEB71","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"285beb29e5e30a7ba8792191178d7f52682884ef","datavalue":{"value":{"entity-type":"item","numeric-id":175378,"id":"Q175378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$BECD4F63-BC19-48E5-A096-91B105D1AA80","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"36245292ed3f481a9afbac2e0b7b7fcb988329ca","datavalue":{"value":{"time":"+2007-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q883232$0E5B36D6-B629-4D7A-8FC6-2F62ADE16702","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"135c9945727b7d5c7a564d172b4531c902d26f77","datavalue":{"value":"https://idus.us.es/xmlui/handle/11441/55008","type":"string"},"datatype":"url"},"type":"statement","id":"Q883232$055AD76C-BE2B-424F-868A-A953537FC26B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ce171116b5c487c1e16b308e8766b9982ae50ed","datavalue":{"value":"Let \\(H_1=(V,E_1)\\) be a collection of \\(N\\) pairwise vertex disjoint \\(O(1)\\)-spanners where the weight of an edge is equal to the Euclidean distance between its endpoints. Let \\(H_2=(V,E_2)\\) be the graph on \\(V\\) with \\(M\\) edges of non-negative weight. The union of the two graphs is denoted \\(G=(V,E_1\\cup E_2)\\). The authors present a data structure of size \\(O(M^2+n\\log n)\\) that answers \\((1+\\varepsilon)\\)-approximate shortest path queries in \\(G\\) in constant time, where \\(\\varepsilon>0\\) is constant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q883232$8AE75232-C9E1-4B8D-BA8E-BBB607811F77","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"a0b3a923a0eff06cabf746e43818055d9a4bb202","datavalue":{"value":{"entity-type":"item","numeric-id":166203,"id":"Q166203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$01127E54-26A6-4E7D-8827-D515FB0EAA4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2ce72165d993b0b8ed97728d731d2db2473b9554","datavalue":{"value":"65D18","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q883232$CE986382-A447-4385-9B95-0985D840DFE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64160bebf18cc7c81be962f661a35da21af54d84","datavalue":{"value":"5161067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q883232$7FC3F9C9-1F22-4EEF-B883-EE02E5EA4345","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"551d108313cfab3a77b395a647aede7021169ebd","datavalue":{"value":"computational geometry","type":"string"},"datatype":"string"},"type":"statement","id":"Q883232$C008C80D-9151-4F69-8189-9257CA15D17F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ca054995312bbd623e61d4b20c5043ba566e6e9","datavalue":{"value":"geometric networks","type":"string"},"datatype":"string"},"type":"statement","id":"Q883232$0D05898F-0046-4583-8483-32F8C063AD47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ab0f102f99a61be25b5b8cb5f7adf0b97b4216f8","datavalue":{"value":"distance oracles","type":"string"},"datatype":"string"},"type":"statement","id":"Q883232$A8EBC719-5682-4512-A516-C807FBADA966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3e37b14edce30440c855a89e32471c921e35655","datavalue":{"value":"shortest path queries","type":"string"},"datatype":"string"},"type":"statement","id":"Q883232$A945CE49-FA71-4DF4-AAE7-6C7555726032","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":"Q883232$C5D4DDF3-07D6-4D3C-92DF-83EAF289F776","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"185a57f2ee2c38b8a1584aa72d0d0859293baea3","datavalue":{"value":"W2116812387","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q883232$8853CB41-CE43-4B5C-AF2C-F44342F2BE63","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1569f5530b9747eba4a828270bb888d9d63503e","datavalue":{"value":{"entity-type":"item","numeric-id":4268701,"id":"Q4268701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$593EB995-A7EF-4AF4-97D5-6C01DFC87273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f29d5232ef41f1d74ad6f96b4d89caf068895dda","datavalue":{"value":{"entity-type":"item","numeric-id":4595512,"id":"Q4595512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$0650FE9E-2329-43A1-A876-603BB7B735D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01f91abdf6291a73a28c0c5d6b9c16690ebd0dc1","datavalue":{"value":{"entity-type":"item","numeric-id":3158524,"id":"Q3158524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$2E0EBB3E-8E26-418F-830B-18AFED13DCFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7a9dd4d0baf2f0086a8eaf23790e5e54c117c15","datavalue":{"value":{"entity-type":"item","numeric-id":5501268,"id":"Q5501268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$46E8FF82-BC1D-4B8E-B462-7804ED86572F","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":"Q883232$CE4331AC-D24B-4BBB-864E-D454C8EC3224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e46012c1e8022041de5d6843e63b4d32e6d7dae6","datavalue":{"value":{"entity-type":"item","numeric-id":4886059,"id":"Q4886059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$842E3BD2-A614-4FEB-9A84-F0C7EFBB00E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb6736f39ca080b94758371fb50de21eee1341ae","datavalue":{"value":{"entity-type":"item","numeric-id":4943866,"id":"Q4943866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$B75DCFB1-88E6-437B-A86A-925E6FE4E9BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"394dd0a1db136114267061e6879ec698b3dcf8fa","datavalue":{"value":{"entity-type":"item","numeric-id":4252291,"id":"Q4252291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$CD5E89D6-932D-4922-BF47-4724040E12D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9562975b659ee36323bc10f44914f734dbe22ea7","datavalue":{"value":{"entity-type":"item","numeric-id":4210144,"id":"Q4210144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$3BE1E075-32FD-4E95-AA7D-2A19F2AFE5C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b989f45b85fa44137ad22092706b6102fd241bf","datavalue":{"value":{"entity-type":"item","numeric-id":78129,"id":"Q78129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$9DB38D1F-B830-434D-851C-A5B676CBA34A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b25b274e4c418261ded7cd1fc46a8f9c565112b","datavalue":{"value":{"entity-type":"item","numeric-id":4943891,"id":"Q4943891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$319703F0-2483-4236-9332-6048E13EBD85","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b7b43c3c62b745ea5d943abc70a6f830e0cdc2","datavalue":{"value":{"entity-type":"item","numeric-id":5096942,"id":"Q5096942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$68FEE1C3-7CBB-4F95-A27B-F62109C6F43B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4ec731eaf7aefc3aebbcedece8462c5829eadc2b","datavalue":{"value":{"entity-type":"item","numeric-id":4252303,"id":"Q4252303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$6BD692BA-6FC9-4F28-AB22-52AFBD45CCC2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6704ccbb4c75ac5e07412c0181b63f464f1b7a0e","datavalue":{"value":{"entity-type":"item","numeric-id":5225293,"id":"Q5225293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$916D9E4B-5EC1-4E67-8B41-07A3172EDF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4bddf54130ed36fd250dd95b7c6dacd4beef135","datavalue":{"value":{"entity-type":"item","numeric-id":4829019,"id":"Q4829019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$025F3D67-FAA7-4C27-9A40-4F6E37EA46DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"07c864494d5b0cd076e63c25cd1e9ebb73bddb42","datavalue":{"value":{"entity-type":"item","numeric-id":4427857,"id":"Q4427857"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$37BC4376-B99C-4D54-891C-4FC00EC3458C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cef6741512165f22e1c64241720200689554371a","datavalue":{"value":{"entity-type":"item","numeric-id":5710703,"id":"Q5710703"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$CC68B286-82D1-4446-977E-E151070F7CDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb3da8b87dda3305b501832e85dafa5e6033c94d","datavalue":{"value":{"entity-type":"item","numeric-id":2956702,"id":"Q2956702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$047E9202-4B2D-4B21-9B37-7B25EC67B681","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a24cef77e7af0be637e251b452afb5eaa8215792","datavalue":{"value":{"entity-type":"item","numeric-id":1608896,"id":"Q1608896"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$4E8FAC30-163F-4D41-850A-3113113EAEFF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ade2e0d4685c3603e1ac21d0c654408026dcd83a","datavalue":{"value":{"entity-type":"item","numeric-id":4401014,"id":"Q4401014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$08D4C6A4-4F65-4DF5-BCC3-33BD30955C73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"131d949eae19a9e99c700765927d99408cfe4f2d","datavalue":{"value":{"entity-type":"item","numeric-id":4323731,"id":"Q4323731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$C2D3AFE6-CFB0-44BF-BE7B-4E80EC8FA71C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"895b5f7c40da52d27736744b4b4669deac7211d5","datavalue":{"value":{"entity-type":"item","numeric-id":4485191,"id":"Q4485191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$C7487961-C313-4CF1-9D05-6CF2DAB400D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57cc2dab6fcd00b3a5ef8504eceb52ca80db67db","datavalue":{"value":{"entity-type":"item","numeric-id":3158540,"id":"Q3158540"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$D031C322-9314-4DED-B13E-75F9DFCFE34D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32e2187ea371ada76056cfa2f23220d87fe44eb7","datavalue":{"value":{"entity-type":"item","numeric-id":5175966,"id":"Q5175966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q883232$E1A8AB20-7553-4983-965F-7ED6C4C932EC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"562ffc9cfb2982d34479a4ec7b90180edbe0c13e","datavalue":{"value":"10.1016/J.COMGEO.2004.12.011","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q883232$A62D045E-38AE-4B1D-97C0-59F5CEE34E4F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ba7f4f42ab9ab02d5571595dcf0347a00a4a98c","datavalue":{"value":{"entity-type":"item","numeric-id":5712168,"id":"Q5712168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09df73cf269e7c7469243efb78d627aa01f3cedb","datavalue":{"value":{"amount":"+0.9911887645721436","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":"Q883232$BA9ED0F9-169E-4FD9-B1E0-DABB9135B881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a08782899c3d35adeb9447b18480a463bb33b6a6","datavalue":{"value":{"entity-type":"item","numeric-id":4829019,"id":"Q4829019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c81b584485656dec95d89d0ecd79a7c44631746","datavalue":{"value":{"amount":"+0.8478708863258362","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":"Q883232$6824DDCD-C3A3-4565-8CFA-6697EBDC5D2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39d472a39978d371f7d47d33d1aec3c4977a7b71","datavalue":{"value":{"entity-type":"item","numeric-id":5175966,"id":"Q5175966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e61baf4a71a1d433f6820138f11c3ba9c72ea58a","datavalue":{"value":{"amount":"+0.8379590511322021","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":"Q883232$CE54E352-6712-41C7-A212-4985270DD9CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b5fe77c78fe6147ee72d959da4128719b740804","datavalue":{"value":{"entity-type":"item","numeric-id":5259601,"id":"Q5259601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1a5612da7392d37a19e1573a59e79383a78373a","datavalue":{"value":{"amount":"+0.8367843627929688","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":"Q883232$ABCB3F35-E0FA-4371-83E7-4BB4160925EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"02133c065aa8df2535335ebd952107a81712b0af","datavalue":{"value":{"entity-type":"item","numeric-id":4962702,"id":"Q4962702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2901e541e9e7499ad1fe554b240f119ba081840f","datavalue":{"value":{"amount":"+0.8361439108848572","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":"Q883232$013A883C-3BA7-49EA-8377-47F31882EF0E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:883232","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:883232"}}}}}