{"entities":{"Q668034":{"pageid":669883,"ns":120,"title":"Item:Q668034","lastrevid":63519723,"modified":"2026-04-11T13:43:15Z","type":"item","id":"Q668034","labels":{"en":{"language":"en","value":"Centroidal localization game"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7032068"}},"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":"Q668034$41EEA344-E2E8-4C00-A1B7-CFD0783E8C62","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b7fd5ae64f25b8e9fb6be084756bf86a0fa395a0","datavalue":{"value":{"text":"Centroidal localization game","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q668034$F9DBDCEF-34F7-4871-BAFE-6F5AD458A55D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d2f6066d0d737b04d41c381882b4049108c664fa","datavalue":{"value":"1406.05068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$8DC124A8-A3B5-4B51-90E7-DE507FADB2AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"01ff5be92d121f7423ad3cd6c581778876c098c4","datavalue":{"value":{"entity-type":"item","numeric-id":251889,"id":"Q251889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$DA80FCE4-7C3F-476F-943B-B98D7194A640","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d94a74181569797e7cff936877b540dc169bb492","datavalue":{"value":{"entity-type":"item","numeric-id":385385,"id":"Q385385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$A428141E-9440-472F-B150-3BCF6E895E66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9efe106b3c39b129b376e8258a66132030c4b918","datavalue":{"value":{"entity-type":"item","numeric-id":282742,"id":"Q282742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$71293E84-27B0-4782-B9B5-1402DA1C1614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cb42e0bc4d37528b917c4e628531b6cae8003e2f","datavalue":{"value":{"entity-type":"item","numeric-id":299057,"id":"Q299057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$494D9C10-EE32-48A5-A749-2848D1A102E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bc5bf07242b72b8c3428d0f5072f63c93bf324d","datavalue":{"value":{"entity-type":"item","numeric-id":282744,"id":"Q282744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$AB873ADF-EB7F-427B-9389-1DB034CFCCAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b5b2a459e0e6ead1b4fde0a38d93b66162ecc50","datavalue":{"value":{"entity-type":"item","numeric-id":271627,"id":"Q271627"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$AC7638E9-2CCE-4B29-87DC-BCA685E84A14","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$D7EC9541-49A8-4C01-AFDD-FBE8986A049F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c236a5296bce37f0e3594963375752714d7f6e86","datavalue":{"value":{"time":"+2019-03-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q668034$3BE23A00-D7F2-450C-B144-8F58E84B055F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c7304377bf5b8eb2eec0e4d1b89de74f68e58d65","datavalue":{"value":"https://arxiv.org/abs/1711.08836","type":"string"},"datatype":"url"},"type":"statement","id":"Q668034$6773EE91-8969-448D-AFDC-0D495B388847","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5bb8efbebd75c1b8844014092d537e3a6ccc2099","datavalue":{"value":"https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p62","type":"string"},"datatype":"url"},"type":"statement","id":"Q668034$60A6E4DF-33F8-4445-9F2F-1F991AB84212","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5e6a98f2854badd18583ba542521dc7c79167a1c","datavalue":{"value":"Summary: One important problem in a network \\(G\\) is to locate an (invisible) moving entity by using distance-detectors placed at strategical locations in \\(G\\). For instance, the famous metric dimension of a graph \\(G\\) is the minimum number \\(k\\) of detectors placed in some vertices \\(\\{v_1,\\dots,v_k\\}\\) such that the vector \\((d_1,\\dots,d_k)\\) of the distances \\(d(v_i,r)\\) between the detectors and the entity's location \\(r\\) allows to uniquely determine \\(r\\) for every \\(r \\in V(G)\\). In a more realistic setting, each device does not get the exact distance to the entity's location. Rather, given locating devices placed in \\(\\{v_1,\\dots,v_k\\}\\), we get only relative distances between the moving entity's location \\(r\\) and the devices (roughly, for every \\(1\\leq i,j\\leq k\\), it is provided whether \\(d(v_i,r) >\\), \\(<\\), or \\(=\\) to \\(d(v_j,r)\\)). The centroidal dimension of a graph \\(G\\) is the minimum number of devices required to locate the entity, in one step, in this setting.  In this paper, we consider the natural generalization of the latter problem, where vertices may be probed sequentially (i.e., in several steps) until the moving entity is located. Roughly, at every turn, a set \\(\\{v_1,\\dots,v_k\\}\\) of vertices are probed and then the relative order of the distances between the vertices \\(v_i\\) and the current location \\(r\\) of the moving entity is given. If it not located, the moving entity may move along one edge. Let \\(\\zeta^\\ast (G)\\) be the minimum \\(k\\) such that the entity is eventually located, whatever it does, in the graph \\(G\\).  We first prove that \\(\\zeta^\\ast (T)\\leq 2\\) for every tree \\(T\\) and give an upper bound on \\(\\zeta^\\ast(G\\square H)\\) for the Cartesian product of graphs \\(G\\) and \\(H\\). Our main result is that \\(\\zeta^\\ast (G)\\leq 3\\) for any outerplanar graph \\(G\\). We then prove that \\(\\zeta^\\ast (G)\\) is bounded by the pathwidth of \\(G\\) plus 1 and that the optimization problem of determining \\(\\zeta^\\ast (G)\\) is NP-hard in general graphs. Finally, we show that approximating (up to a small constant distance) the location of the robber in the Euclidean plane requires at most two vertices per turn.","type":"string"},"datatype":"string"},"type":"statement","id":"Q668034$F95A6279-2BDA-451E-A2A6-0901C27F8D0A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$19130C26-D2B4-4D6F-BAF1-2A9819B0DB72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$665743B2-55FC-4081-B265-D188E8D5AE8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5fbd0918ba2c4a1aeddd30d9d3d146d9773f1239","datavalue":{"value":"91A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$161E0FB7-339A-4E1B-B60A-B0D39065A842","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"0556c939d5f80905b689a8f78ecccbf9dd8e2697","datavalue":{"value":"05C82","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$D474C291-F754-4AF5-9D4D-3B002D63EC4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"93a3b81c31fcfc46ec689a3a12f8f7f9739df81e","datavalue":{"value":"7032068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$6F33268C-669B-4763-9BDD-0380265D9D52","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"10c23af7485feaef9326463e0f649be6c7cec204","datavalue":{"value":"cops and robber","type":"string"},"datatype":"string"},"type":"statement","id":"Q668034$0F21C853-99EE-491E-9F64-4FC3FAB2071C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b322c03f72bfbe9e7516683225803e7e94a5704f","datavalue":{"value":"graph searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q668034$17FF167E-97C7-4E9E-8B88-00698471CBB2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3fe4fabbe15c374b3531ed45dc9baf54b0bb77c","datavalue":{"value":"outerplanar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q668034$47C3D616-4B73-4498-8E33-7854BF250BC3","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":"Q668034$99FF75B0-050D-4D51-BC79-3B78D8E707A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9d3f589cc14fdb4d9cef9a89f1a1d0804432c89","datavalue":{"value":{"entity-type":"item","numeric-id":4035355,"id":"Q4035355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$D77DB905-6800-4C7D-A903-2D0FB75C451E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5c3621fda226d63b97459ecba54d0ccbaa4baef","datavalue":{"value":{"entity-type":"item","numeric-id":3090934,"id":"Q3090934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$D55932CA-DBDE-4A23-AF34-43EEAF164BFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c8c6f7e6b659084157bfcd5694b6be1bca7ef662","datavalue":{"value":{"entity-type":"item","numeric-id":1627842,"id":"Q1627842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$ED72ABE3-E23D-4102-8355-247B0E0CAD9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5476aaa168ef66312d2404f29ceebabf7ffce508","datavalue":{"value":{"entity-type":"item","numeric-id":2410225,"id":"Q2410225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$35448233-50E7-4B15-B3D2-A788F6F4354B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4d523768c153b175d04c56ad99e0a7c7a1b2da02","datavalue":{"value":{"entity-type":"item","numeric-id":1929218,"id":"Q1929218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$73D729BC-A369-467E-8655-16CA09EEF05E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ef11328b0a874b17b6c515cc02f7431b8fb3f25","datavalue":{"value":{"entity-type":"item","numeric-id":4642472,"id":"Q4642472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$14E12376-A81E-4EB1-9CB8-E601468B1BA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"abeb9cafb8b331288dc8ea848baae4b0563e8209","datavalue":{"value":{"entity-type":"item","numeric-id":512651,"id":"Q512651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$2F73CE6C-B4FE-4B68-B0CF-7F2A82218EB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11faf7b9940bfc3311a6963243413a0cca8f6d9e","datavalue":{"value":{"entity-type":"item","numeric-id":2408094,"id":"Q2408094"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$DB500831-91AA-457B-B71E-E7F6A71FB515","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7cd472af80523eb239e1437aa7fbccca41b12e7","datavalue":{"value":{"entity-type":"item","numeric-id":4119237,"id":"Q4119237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$5CC71C71-2C16-4ECF-95AA-9DA004A0D3C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dcbe5765160b5b77360a651a6f2e8d2b771ae0c3","datavalue":{"value":{"entity-type":"item","numeric-id":2411615,"id":"Q2411615"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$78965E16-B1AF-4C6F-9C7C-EC692D140F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee1ec3e679277531ddeee1652cd1faae98a96c8f","datavalue":{"value":{"entity-type":"item","numeric-id":4400275,"id":"Q4400275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$E96A5E8D-0222-493B-A04F-DB0B10EFD45C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1bbb01b5f3c47526c0a1fa33d670f8287107a08","datavalue":{"value":{"entity-type":"item","numeric-id":713142,"id":"Q713142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$EAA80D6D-AB5C-43EC-B51B-AA38061B4602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8a24c8db5b93a513f93ca74ff648b35c878a3cb","datavalue":{"value":{"entity-type":"item","numeric-id":2453120,"id":"Q2453120"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$348575C6-E82C-460E-B307-383EED703BEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1a52d109a946993fa4a3f0a29b8406147954b2","datavalue":{"value":{"entity-type":"item","numeric-id":4075485,"id":"Q4075485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$2342D05A-C615-461B-BA13-4FE298A8D09C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3b965fecefbf97ebea4be9bc23a5a8a1bbee43c","datavalue":{"value":{"entity-type":"item","numeric-id":3786298,"id":"Q3786298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$CFF2F49D-539F-4C30-8218-B49FFCF6B0D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"43bff87aa69a57c9a0aeef11f5f932793665b7fe","datavalue":{"value":{"entity-type":"item","numeric-id":3803159,"id":"Q3803159"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q668034$44C27F97-9CDE-4499-B11B-CB0C9E156035","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"ab129f271b69e319a065bdbc05ff15b8105896b0","datavalue":{"value":"bafkreifgfyn5lkgl3zqvip4h7g6jemmg6juqoi2oeymbdauthefqay6eby","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q668034$4DC1CA82-D93D-46F3-B1A2-B4FB354C2EEC","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb2696f4a54cc09247a7a85071c91ee6a361952a","datavalue":{"value":{"entity-type":"item","numeric-id":5918179,"id":"Q5918179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d484babce13e875e6c45e42ac1a4499c43942926","datavalue":{"value":{"amount":"+0.8660374283790588","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":"Q668034$83724181-EA75-4BB9-BF47-AA71040E1F79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b9fb83875dcc11d9e72fca8b6c4522e8cbf6d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1627842,"id":"Q1627842"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5819e4a92d4127df0bb1845961dedec0b4ac1089","datavalue":{"value":{"amount":"+0.8441404700279236","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":"Q668034$2C991115-680C-4D2B-9041-AAC22715711F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0bbbc35e8601f97ac1087b2dd5b31cc38050b116","datavalue":{"value":{"entity-type":"item","numeric-id":5916085,"id":"Q5916085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5d36e384971c089e41c062576b147b6b8b4f7756","datavalue":{"value":{"amount":"+0.8279503583908081","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":"Q668034$8FDC0B8C-2C87-4FEB-A7CC-33A4E015FB78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f062bc200d29be783ef0f726b9ea4a06c2dfe29a","datavalue":{"value":{"entity-type":"item","numeric-id":4642472,"id":"Q4642472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"426462298f8b57550484bed8ed86b89a45937be8","datavalue":{"value":{"amount":"+0.797083854675293","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":"Q668034$E02B34FD-9375-4D12-AFBF-5BDD4BE86414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cc99f58900565cc3049fe453d23215968a78712","datavalue":{"value":{"entity-type":"item","numeric-id":713142,"id":"Q713142"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3bdb5c3812a7ed02b01c49a1b335b04ac8990dc0","datavalue":{"value":{"amount":"+0.7930831909179688","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":"Q668034$3B34AEF0-F209-478C-B4F4-7FBB4C08979C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Centroidal localization game","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Centroidal_localization_game"}}}}}