{"entities":{"Q2429323":{"pageid":2440066,"ns":120,"title":"Item:Q2429323","lastrevid":74310327,"modified":"2026-04-14T19:28:49Z","type":"item","id":"Q2429323","labels":{"en":{"language":"en","value":"Ping pong in dangerous graphs: optimal black hole search with pebbles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6028455"}},"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":"Q2429323$D7628207-3CEF-4024-AE0E-5D0E49AF7E60","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"cdcc60f4e5c06d573284268c413d7fccb7e36349","datavalue":{"value":{"text":"Ping pong in dangerous graphs: optimal black hole search with pebbles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2429323$2EE850A6-4BED-4E68-9262-0C39EE661B1F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4771987a2fbb0697a273c1d4f4eeaeb0a29d57e9","datavalue":{"value":"1247.68028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$924168D7-0C80-4224-A381-7A1F77F5B5F3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"05b3dbc591d405b104c55b2c07b37b34506405a1","datavalue":{"value":{"entity-type":"item","numeric-id":557815,"id":"Q557815"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$FFEC39CC-9AFD-4FA0-9276-A9237440A9E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0c953cb58330590f2c9d911caeaec822e1c39e33","datavalue":{"value":{"entity-type":"item","numeric-id":265065,"id":"Q265065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$2272C91A-F5BA-4F0A-AB85-F7F56DFE55CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"db6df3606e104c2161180e2597803fd70c72d072","datavalue":{"value":{"entity-type":"item","numeric-id":557817,"id":"Q557817"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$86A6DC02-5AAC-4006-850F-2C1129A75606","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":"Q2429323$8E8FF6D7-63C0-43EE-B6A7-4B3402A7A3ED","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"52b04daa1d703ea977748e4d42defef3819c2dd9","datavalue":{"value":{"time":"+2012-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2429323$B78B3B47-056F-4935-B0E9-561F0955D2C5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"223824aaa03eb5c015aa3f988f81c8b5d14ed5fa","datavalue":{"value":"This paper studies the black hole search (BHS) problem: a black hole is a vertex where any incoming agent is destroyed without leaving any detectable trace; black hole search is the problem of determining the location of a black hole by a team of identical agents. This problem has been studied in several settings, under a variety of assumptions on the power of the adversary and on the power of the agents. This paper considers the weakest settings that still make the BHS solvable. A first setting is the whiteboard model: every vertex provides a shared space for the arriving agents to read and write. A second setting is the pebble model; it is provided by identical pebbles that can be placed on nodes, picked up and carried by the agents. The main result of this paper is that the pebble model is computationally as powerful as the whiteboard model for BHS in networks of known topology.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429323$5B84F3B0-BA4B-46F6-A7E2-33C420602F0B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"62ff42057022552eaa82447a5a1563ef3bf93acd","datavalue":{"value":"68M14","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$6D1A8D63-E031-497B-9405-0C938ED86704","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$D688D82B-940C-4991-B894-AAAA058B508E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a0dc380a7a6964f00e6560e4112710836960e832","datavalue":{"value":"68T20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$DE7EB4FA-113B-4940-9456-8181AC75C969","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c97df88540c7e7c9950e190664db88c514818c74","datavalue":{"value":"6028455","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$21DD0F22-E3E3-4A4D-B732-AC249F21FA94","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b36d924addd0d2f364b26835d91730b673a9f92","datavalue":{"value":"distributed computing","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429323$4A41E635-5419-4461-A197-F39C220B8F29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2bb610b7129e45c2757b3d6941cebe1b38af2df3","datavalue":{"value":"graph exploration","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429323$4A0F5456-1A80-477A-A2C6-1DC06CBF0876","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3276933d1a0a9ceb8ecc762d4e4b251637260ed3","datavalue":{"value":"mobile agents","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429323$157E72C9-83F2-465F-8AE7-5F810BA256F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cfa530abbbf3c263bfda8a22c0625877db212595","datavalue":{"value":"black hole","type":"string"},"datatype":"string"},"type":"statement","id":"Q2429323$DDC35C1A-E659-4486-B8F7-3746B95C5B95","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"e58c6dffa2cb5b51020de9c6757ee2fa56512d39","datavalue":{"value":{"entity-type":"item","numeric-id":690236,"id":"Q690236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$D730BB39-2EED-4AC3-9648-CC5945482EF4","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":"Q2429323$A295D674-A4D6-42EC-84C0-F6804E1E17B3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2f9158d172ac1cd5411ddd87141288ff95430e30","datavalue":{"value":"https://doi.org/10.1007/s00453-011-9496-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q2429323$1E23D687-FB51-4C8A-BBA5-0720BD78C72A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b6b152f8dc2f9a3ac21b0ed0ec3bcaaa345294a3","datavalue":{"value":"W1967767406","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$743ADEA7-F3DD-4C5F-AFC0-B0138524A8B1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"89a576f8d43fe32d9c28008fe1b7e7c1cc57a425","datavalue":{"value":{"entity-type":"item","numeric-id":4943862,"id":"Q4943862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$B133857F-90D6-43CB-AA55-ADE8FAFA4074","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2bca05c0050609e2151f4f24ca92928a5a211ee","datavalue":{"value":{"entity-type":"item","numeric-id":1854539,"id":"Q1854539"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$65F3EBF3-1234-4D66-AF3F-BDED94EB9E75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"47dfe8a208fd565bab466f97fea04c121a2bd4ef","datavalue":{"value":{"entity-type":"item","numeric-id":3523202,"id":"Q3523202"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$DFF4C260-3E98-440F-A3CB-123F4BF9D302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7eaf655bc7a2af474e0cac7c687e57f8baee6468","datavalue":{"value":{"entity-type":"item","numeric-id":3408170,"id":"Q3408170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$C1CEB472-885A-46B5-92A0-6FE2D75D739B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e55cb05e6d0f0717ce07ca2cfa7bd3e589dcc7e","datavalue":{"value":{"entity-type":"item","numeric-id":5480656,"id":"Q5480656"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$FA230A5B-872A-4724-BDCC-088E377BEDE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac5d77eda837861471df468609a646da36a8dff8","datavalue":{"value":{"entity-type":"item","numeric-id":5437234,"id":"Q5437234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$0FF4844C-03DC-4725-82C2-126A7802FB4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"32b9ba91de09acbd0115791ffd69721300cb7427","datavalue":{"value":{"entity-type":"item","numeric-id":2456354,"id":"Q2456354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$CB1B82DC-AF9A-4489-8826-8F5D674C5B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bd5e315dee24833078d01dc1a0b6ca9df96317a","datavalue":{"value":{"entity-type":"item","numeric-id":4718736,"id":"Q4718736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$ED3B5DE5-2009-425E-B553-AFD4D89A3542","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7270946ef3896d650a35ab97433b07f99521f244","datavalue":{"value":{"entity-type":"item","numeric-id":1954192,"id":"Q1954192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$EF8C37EF-2257-47D9-A6D9-473A9F0823AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f9564de358ed29b2581846af2917440f473d7db","datavalue":{"value":{"entity-type":"item","numeric-id":996708,"id":"Q996708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$282E7659-9C7C-443E-9904-6FF54E1ECDF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fbe30f082cd41067b3e9a3f3fc0ff52a00c2f680","datavalue":{"value":{"entity-type":"item","numeric-id":3434551,"id":"Q3434551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$46D0D2B4-4E3E-4896-803E-8C7F5200DFAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"502368479b5b7934b36f24ecc28f7ec0b66e7ec1","datavalue":{"value":{"entity-type":"item","numeric-id":3540233,"id":"Q3540233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$E6FB91E8-2CB8-449D-AEFA-0C4DB54AACCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f0e26afea86987cbf129994875443af80c30440f","datavalue":{"value":{"entity-type":"item","numeric-id":3423884,"id":"Q3423884"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$64A9DF72-A6DC-46B7-AF61-F0CA496EFD32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be00b379df935e5d1164223bdf0a8f20408ba2e3","datavalue":{"value":{"entity-type":"item","numeric-id":2575752,"id":"Q2575752"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$8369889C-0E0B-43ED-B1BF-4B4E0021C275","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"576ed90076cc26dae6d14114ba5b2aec42a2f9f6","datavalue":{"value":{"entity-type":"item","numeric-id":3548722,"id":"Q3548722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$C9C71A41-2F1D-4EB1-BBA7-825882AB5E31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eb2ede0661ab31abea7475d337ff2a1308bb4d9b","datavalue":{"value":{"entity-type":"item","numeric-id":2382674,"id":"Q2382674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$3BCCE928-4A3F-4625-A869-281B7EC292D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6d3386b06b28e9b82fdee2a79406ca073145a851","datavalue":{"value":{"entity-type":"item","numeric-id":3569123,"id":"Q3569123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2429323$96387835-B086-4872-AABE-E284A253D939","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7d207574931771b29d1c8ac42c926ce0753fd1fc","datavalue":{"value":"10.1007/S00453-011-9496-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2429323$1A495419-C2E5-45DC-9EDA-24FAF8451B06","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1f46ba2fb7ae7433ba35ad50b9bc6bc664c29f5","datavalue":{"value":{"entity-type":"item","numeric-id":3540233,"id":"Q3540233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13641f171bf334efcba353c373f833f751d781c5","datavalue":{"value":{"amount":"+0.9094749093055724","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":"Q2429323$979E6C3B-C63B-49CD-A5D8-438FDF9170BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f205df859cf21a381e4d0cb90dc53be3c1834d7","datavalue":{"value":{"entity-type":"item","numeric-id":1954192,"id":"Q1954192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2fb4eebe0a0291412d6e112521c446ec44ac7cee","datavalue":{"value":{"amount":"+0.8118494749069214","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":"Q2429323$BBA67E33-BA39-4846-BE16-48142D725464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba0c3015bcdff8f9979526609d7fe95fc0e9a157","datavalue":{"value":{"entity-type":"item","numeric-id":5710084,"id":"Q5710084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"03efc3a13c8d21714121c906c7e9381ba54cd563","datavalue":{"value":{"amount":"+0.8065287470817566","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":"Q2429323$4DED2B38-C93F-42DD-90F6-9F9A8FF60E33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05c3c45ecaf2614da17274f5799fd129fe428070","datavalue":{"value":{"entity-type":"item","numeric-id":3066443,"id":"Q3066443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9a38a2668409ff46e23c542b7212900942764cc3","datavalue":{"value":{"amount":"+0.8011244535446167","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":"Q2429323$FAF370DD-DA61-4238-BDB0-374C682787D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e38d611e7310dd0c4fe447b91ab3a0b777561625","datavalue":{"value":{"entity-type":"item","numeric-id":996708,"id":"Q996708"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4cda7c6c2d89fc7b6189d758408b2f69ec866c6","datavalue":{"value":{"amount":"+0.8000407218933105","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":"Q2429323$8D565DC0-AAFE-492E-9D27-21EE893C0DAD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Ping pong in dangerous graphs: optimal black hole search with pebbles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Ping_pong_in_dangerous_graphs:_optimal_black_hole_search_with_pebbles"}}}}}