{"entities":{"Q2345464":{"pageid":2356207,"ns":120,"title":"Item:Q2345464","lastrevid":43916721,"modified":"2025-11-17T14:13:30Z","type":"item","id":"Q2345464","labels":{"en":{"language":"en","value":"Connected surveillance game"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6438855"}},"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":"Q2345464$468150FF-CB0F-47AC-BF6F-59131BCE19A6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6d3ff012f2c0cddebd1f0ae587964cce89a266ce","datavalue":{"value":{"text":"Connected surveillance game","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2345464$B31D2760-893F-4CC5-A9CD-CD1440D3824D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b8abaf08c74ea090abf5de924073fff2fd74d650","datavalue":{"value":"1348.91071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$3788BB8B-E5D1-4D92-AF53-30949864DA76","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a654db2557b20e562583b1d86e7981017badff3","datavalue":{"value":{"entity-type":"item","numeric-id":1660912,"id":"Q1660912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$0D62A8CF-2FDA-498F-9699-E946AD1997D6","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":"Q2345464$612BC320-62E3-4064-A810-321C159447A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7708d5b604aeb0233e883f7ff478054769e3fc4b","datavalue":{"value":{"entity-type":"item","numeric-id":1939270,"id":"Q1939270"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$BBEE36EA-0B35-49C5-AF1B-A4E9F4DA2A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7564af6a333f74fa77e6092e0f42c2f842ccbd13","datavalue":{"value":{"entity-type":"item","numeric-id":325417,"id":"Q325417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$909BA0C9-7DA6-4B1A-B5A1-402AF75FD8E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"04ec700e061bdb189aab9730bc61f65cc50739ee","datavalue":{"value":{"entity-type":"item","numeric-id":638537,"id":"Q638537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$BEE67F8F-C87B-488D-A4EC-AF12A2FA7999","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef68b7c0aa326ec2b84f9b3c3d8dc51f2606c44","datavalue":{"value":{"entity-type":"item","numeric-id":166298,"id":"Q166298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$F53C70D9-2537-4787-AD27-F5020CE19326","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$656A9FF8-D771-4142-9684-62384C5EBD70","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ccdd437656ae39926623dbd87596e190124636a","datavalue":{"value":{"time":"+2015-05-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2345464$ED791566-37E7-4157-89B3-3FE18FE41815","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"391f266f50451af7c953ab0eda9be7ea10d3fafe","datavalue":{"value":"The surveillance game is played on a graph \\(G\\) by two players, the surfer and the observer, as follows: Initially, the surfer stands on a marked vertex \\(v\\) of \\(G\\) with all other vertices of \\(G\\) being unmarked. Then the two players alternate with the observer marking \\(k\\) vertices of \\(G\\) and the surfer moving to a neighbour of its current position. The surfer wins if at some point it manages to move to an unmarked vertex. Otherwise the observer wins. The surveillance number \\(\\mathrm{sn}(G,v)\\) of a graph \\(G\\) with initial vertex \\(v\\) is the smallest \\(k\\) such that the observer has a winning strategy.  The game can be used to model web-page prefetching in which the web-browser aims to download web-pages before the surfer tries to access them.  The connected surveillance game is a variant of the surveillance game in which the marked vertices need to always induce a connected subgraph of \\(G\\). The connected surveillance number \\(\\mathrm{csn(G,v)}\\) is defined analogously.  Of course, \\(\\mathrm{csn(G,v)} \\geqslant \\mathrm{sn}(G,v)\\) but examples where \\(\\mathrm{csn(G,v)} > \\mathrm{sn}(G,v)\\) seem hard to construct.  In this article the authors prove that \\(\\mathrm{csn(G,v)} \\leqslant \\sqrt{|V(G)|\\mathrm{sn}(G,v)}\\) and provide examples where \\(\\mathrm{csn(G,v)} = \\mathrm{sn}(G,v) + 2\\). They also investigate an online variant of the game in which at each step the observer only knows the neighbours of the marked vertices and not the whole graph. Furthermore they prove an NP-completeness result related to the game.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$881D7E05-9BD9-4ADC-806E-84EDD251EC7E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"fe719ac6b13db778b87ec3647531213541412700","datavalue":{"value":{"entity-type":"item","numeric-id":396928,"id":"Q396928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$81D58DCD-5270-497D-9E27-653472C8FA47","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$B5E10024-99C8-482A-B994-2EF7CE35C819","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$33B5CFF1-F7B2-43C8-81D6-F5D7BB3EFA75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$668B33D5-BEAB-482C-8D9A-9FAAE9374880","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b92b64cae3ba93e9005a12152ea9a8f80a25ee3","datavalue":{"value":"49N75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$DE4D5D08-0678-44C6-9A6E-10C185A91A80","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6ed41cad669c72e1685769e48d3e3e8fd815676f","datavalue":{"value":"6438855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$92B22158-7526-4565-B826-C863B0B631CE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8b7b4ca249a7d96f4a8c4ef5c902acc06134665","datavalue":{"value":"surveillance game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$3458C626-95C7-4F5F-B77C-E9C8070CE47A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7371f63b6aa7ab1ae7396a76983ac529c916bce3","datavalue":{"value":"cops and robbers games","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$356E812F-51E3-4299-A2A5-7B254DF0DA19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8668772853262dde2f8109e115d3ecbcd9c5fcb","datavalue":{"value":"online strategy","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$A33FFBBA-AD01-4F95-960A-61EB5E4C9FAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c15ea06d808af5c0a1bb7dbc19f9d0e8573cab86","datavalue":{"value":"prefetching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$8FF4A94E-EAB7-4A6D-A9F3-B7EA0DAEDEC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8882da51632bee66a11709fd17fc33340bf2f09","datavalue":{"value":"pursuit evasion games","type":"string"},"datatype":"string"},"type":"statement","id":"Q2345464$D01A8AD7-2932-4AD8-807C-1F3C19629F76","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":"Q2345464$37635F7B-24CE-405F-8598-F7BE364B1461","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cdb5166729321490f3bf2f3eec5e9d2dbeaba9a0","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2014.11.025","type":"string"},"datatype":"url"},"type":"statement","id":"Q2345464$1D7484DB-8026-4CE2-A8D6-4FB95BD15932","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"399684d65219202f2a1ae6b1382a2547eb46f06f","datavalue":{"value":"W4206248279","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$F59EB89E-BC17-4744-81D0-290579061BFE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"41fc5d688bdc4bee937c8677165a628873949b67","datavalue":{"value":{"entity-type":"item","numeric-id":2437758,"id":"Q2437758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$2F307698-09AD-4508-BC7F-68F66B115E16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b382547d8fad964f6c32dd98e9936f8afb92f192","datavalue":{"value":{"entity-type":"item","numeric-id":1230637,"id":"Q1230637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2345464$8F3933D2-834E-488B-A9E1-6EC9889D6EFE","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3b7916234927881769a205223a79cbeb934b02e8","datavalue":{"value":"10.1016/J.TCS.2014.11.025","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2345464$8D5A8F8D-D07A-46B9-840B-EC4CCC507D99","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5807ef018159f02f9774ad2958f674ff5c0e67e5","datavalue":{"value":{"entity-type":"item","numeric-id":2868632,"id":"Q2868632"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5631658f982e69d4666606bc668157d8d900719","datavalue":{"value":{"amount":"+0.9999995","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$07D8FEFB-20B0-4734-A8C0-F86B041AC060","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"195d478bd97dfbb502b8146adc8370a3471cef33","datavalue":{"value":{"entity-type":"item","numeric-id":2818070,"id":"Q2818070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d42be763cc654794f8af32f277b916f709df518","datavalue":{"value":{"amount":"+0.8175171","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$94B154A2-A63E-4BFC-B61A-5FB0EEE17356","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a424d3e618a72a3344725a1156d5d77e5fecc2cf","datavalue":{"value":{"entity-type":"item","numeric-id":3542383,"id":"Q3542383"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"450c3204af7814c719fb8f300a8427d809a70e5f","datavalue":{"value":{"amount":"+0.79494387","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$6BF514E3-B9EB-4B68-A9CB-857ED9162257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"866319d966d22f3da6f4e910df164679d0874418","datavalue":{"value":{"entity-type":"item","numeric-id":5028806,"id":"Q5028806"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"940c17cf64def954119ff66685a940571cc46f1a","datavalue":{"value":{"amount":"+0.78603524","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$63C7FA82-E756-48DF-AF0C-8B238B2F9921","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0427bb072d058d292da90de801f4c45e73fbc6ca","datavalue":{"value":{"entity-type":"item","numeric-id":2879520,"id":"Q2879520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d2ffaf6d5dc4bf58ede79d84843ae84b887d02c","datavalue":{"value":{"amount":"+0.768877","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$421A3D0A-7C4E-488B-8B90-6F1664DBC003","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"edb664393d836421edcff59b6ff0062e9ef157f6","datavalue":{"value":{"entity-type":"item","numeric-id":2936999,"id":"Q2936999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2934c19148dcb149254091fb62e77325e91b2363","datavalue":{"value":{"amount":"+0.76691407","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$F2CC3287-6B57-453D-860B-0A2A518E6D86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"48bd95112105fba6180b871a90d314d1ae2a45c1","datavalue":{"value":{"entity-type":"item","numeric-id":507326,"id":"Q507326"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f6c623d7b9bf30ef486a016ef6a8f5feaa41baab","datavalue":{"value":{"amount":"+0.7666676","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$DBB9B3DE-A64D-4DE0-868F-638B0E83F969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e3f75d8f58fea81b13172721eeba981014d5de93","datavalue":{"value":{"entity-type":"item","numeric-id":3489819,"id":"Q3489819"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2da026bb8db4d2f3bb82f22086b935b82219275d","datavalue":{"value":{"amount":"+0.76401746","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$9FD17D21-C000-49C0-B50D-0D09D140333A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"829f78bf8f961d217c1d211578dd61f1c467ad60","datavalue":{"value":{"entity-type":"item","numeric-id":5075367,"id":"Q5075367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"afbf495bfb02fdbcca4fc33c2dfcf5d2551c2e4e","datavalue":{"value":{"amount":"+0.76290774","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$C9D7B2BC-63F1-4E27-9C89-5CBBAA8A43FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"98b07637220032658fcbcf8c81235af346720314","datavalue":{"value":{"entity-type":"item","numeric-id":5060487,"id":"Q5060487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"95d24405e13c5a5d2440e2f71697b5b494c4fb2f","datavalue":{"value":{"amount":"+0.76046854","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2345464$A16A50B2-F064-4BCD-A809-3423D1F6B64D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2345464","badges":[]}}}}}