{"entities":{"Q2062677":{"pageid":2073419,"ns":120,"title":"Item:Q2062677","lastrevid":57233664,"modified":"2026-03-27T14:24:26Z","type":"item","id":"Q2062677","labels":{"en":{"language":"en","value":"Guarding a subgraph as a tool in pursuit-evasion games"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7451244"}},"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":"Q2062677$AAC9B2B2-47DC-4957-B365-8DEE06BCD0E3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2884acc548a1e2ec14b366a0f69e80bf8187f4aa","datavalue":{"value":{"text":"Guarding a subgraph as a tool in pursuit-evasion games","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2062677$A6BAAD49-CC74-49E6-BFAC-B6EE84277092","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"61fad6c4e8c1ddcc0ca8150fbc9e3af8910a7876","datavalue":{"value":"1483.05101","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$FEE33045-2CD6-4F2D-904B-365DF206CFAF","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd1d9938c60ed1948da129997586fff04f239dff","datavalue":{"value":{"entity-type":"item","numeric-id":244508,"id":"Q244508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$33A5F756-7EA9-4599-871C-344838E5C66E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7449c2342f090cf7addd0f2fe6125b82b8b219ed","datavalue":{"value":{"entity-type":"item","numeric-id":412341,"id":"Q412341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$7667D90B-0B9D-436B-8E70-087159660BF0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"af49efd26010b4160b051c86a282dcb3745069b3","datavalue":{"value":{"time":"+2022-01-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2062677$18177CAC-CACC-4417-B061-037F2C00E89E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"110c27b061e40ffd4e3b87ba3ce3df6cfbc94b75","datavalue":{"value":"Pursuit-evasion games on a reflexive graph \\(G\\) are games in which several cops search a graph for a robber. Both characters move along the edges of \\(G\\) and the robber is captured if a cop steps on the vertex the intruder is on. This paper studies the idea of guarding a subgraph in a pursuit-evasion game. Guarding a subgraph \\(H\\) of \\(G\\) is defined as setting up \\(H\\) such that if the robber enters \\(H\\), he can be instantly captured. In this case, the cop can be thought of as a guard and the robber as an intruder. This paper formally introduces this strategy as an algorithm, proves a characterization of games when a single guard can win against several intruders, and most importantly, it introduces the idea of a robber shadow. This is defined as `the maximal set of vertices from which the cop parries the protected subgraph'. This paper shows that this shadow, and thus algorithms for a successful guard and for a successful intruder (if they exist), can be computed in polynomial time. Additionally, it is shown that the shadow functions generalize graph retractions.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$72FBA390-1E0F-4925-B4A0-0FCA1FA09510","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"61aacb326b9016e73ab7a18800effe4a33425a59","datavalue":{"value":{"entity-type":"item","numeric-id":822751,"id":"Q822751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$E06EBCF0-6415-49F9-94EC-F3129FAAB70C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$D3421B21-7A52-4552-9C2B-1F8AD28874DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$8129FEA6-5441-4ACD-A3F5-56993DF4BCA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$DBEF8A9A-FE9F-48C7-AD6A-3EC801BBDE8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23eabea2f37667b79d34f4282bba7b6c227abf51","datavalue":{"value":"94A24","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$FAB59DAC-8569-4FAB-9C08-82971A33955B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5643657984f548c36fbaea0ffbea883d1494130","datavalue":{"value":"7451244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$5E91AB81-C134-4155-90CF-F3D95C8D4B18","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9d08f123bccccfcd6c7fe77aa14fb8474eb8e006","datavalue":{"value":"pursuit-evasion game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$EC46A17B-247E-478C-B9C8-4267FF723710","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b322c03f72bfbe9e7516683225803e7e94a5704f","datavalue":{"value":"graph searching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$E60C202A-DA0F-495D-897D-87E1DA0FBC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"35d4289385a4d9b393bae1b3a5dddcae4512592c","datavalue":{"value":"guarding","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$276559F3-4589-4632-9146-6D5A603ABB20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b78dd7213a40a8a56f73920f6266a55fd5654007","datavalue":{"value":"shadow function","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$4C915A8D-EFF7-4527-8CEB-724420C52318","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7b820f0ecee188bf9c063b44aa1dcea6f449c9c9","datavalue":{"value":"graph retraction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2062677$B89B0497-B0C9-43BA-9410-B737438662A8","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":"Q2062677$85CC56FA-91A3-42DE-8EF9-93668683674F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6ba1618ea1dbe2d478b56e7b43ae984dfed4b2d9","datavalue":{"value":"https://doi.org/10.7151/dmgt.2244","type":"string"},"datatype":"url"},"type":"statement","id":"Q2062677$C09E9A47-6CA6-4A2E-B88D-3F3301C53780","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"088461a5f127e5029a60fd538756128d62c8f5d2","datavalue":{"value":"W2980952384","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$7B21E18D-9211-4606-8D86-94EB69B7D32D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"c10880db3512cb44b0c7a9adcd35842c8fcabb1c","datavalue":{"value":{"entity-type":"item","numeric-id":793755,"id":"Q793755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$E2C544D8-D97A-43EE-A49A-7C57F2F0B5DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de271bc98faea784dba49f7dbe2a8ec41708fa09","datavalue":{"value":{"entity-type":"item","numeric-id":3418339,"id":"Q3418339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$31C8EBA0-322E-478B-A505-B60A36658BBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b15858e3523aa4f4bd5b67a1cc70b681936adc0d","datavalue":{"value":{"entity-type":"item","numeric-id":1101027,"id":"Q1101027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$CC36BFB1-8551-4A44-8135-4A7CBC43441A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1cf5f19f2d6beedeb98186485341f4ed5445909a","datavalue":{"value":{"entity-type":"item","numeric-id":5387056,"id":"Q5387056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$54E33FF1-5A62-4222-9820-5A0291F86A0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"23fbb2ced497ca7f029a6a40ed44d4b2408bc8ec","datavalue":{"value":{"entity-type":"item","numeric-id":5461685,"id":"Q5461685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$A1A00A82-A2C1-40A3-A7D3-38B8180EC985","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75d4076d4897ab3cc8f6948af493950051b74467","datavalue":{"value":{"entity-type":"item","numeric-id":1127870,"id":"Q1127870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$D5AA6501-CC42-4331-A225-3DC062CE1BB7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"42dd509cf5c6684d522f473ff449f707935cd07e","datavalue":{"value":{"entity-type":"item","numeric-id":652526,"id":"Q652526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$058BC0A1-1BCD-47F7-84DB-EEE879D76C3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fda738d8b3ced668f527abc4ae361c077e3837d","datavalue":{"value":{"entity-type":"item","numeric-id":650877,"id":"Q650877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$2CEA85E4-6671-49C4-9FAD-A4655C25892C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4fc938bd8c0c7b17382aa0fa1cd7652406e0ce2","datavalue":{"value":{"entity-type":"item","numeric-id":2433710,"id":"Q2433710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$81C1BABE-8A21-4C52-96ED-6BBC9E598CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd8a4d0b7750ebf6c90c2de5ecb15c03c7fbe5f1","datavalue":{"value":{"entity-type":"item","numeric-id":5321698,"id":"Q5321698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$C7914080-541C-4A86-B6FA-9A01A673D123","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcd7542caac5915c8f63a224b76605abf20c2235","datavalue":{"value":{"entity-type":"item","numeric-id":1837707,"id":"Q1837707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$9813E2D0-D424-459D-B813-09433716DE41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87ecca2ff62f641884d2d9a89d1b8049fca4b34d","datavalue":{"value":{"entity-type":"item","numeric-id":1072462,"id":"Q1072462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$C124CD40-42CF-4435-896C-08B1082706F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aec7a5195d839105a9eaed2e0df2aa8b7b1aebe","datavalue":{"value":{"entity-type":"item","numeric-id":4159394,"id":"Q4159394"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$C9BC4E18-1555-4643-8E60-FBA0F9EFB4E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c99d22d0171d868be28e3c9ef99bb78cfe951209","datavalue":{"value":{"entity-type":"item","numeric-id":3651572,"id":"Q3651572"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$1053D410-93C8-4C8D-81C6-E5B63A117CE1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3714d0f7c18992470fe00a89dfb049f220572817","datavalue":{"value":{"entity-type":"item","numeric-id":3111664,"id":"Q3111664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$C22B4BDE-269A-4654-B539-56A7D40645F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c525b4b0d940b89b99ec4817f55af5e038299d31","datavalue":{"value":{"entity-type":"item","numeric-id":389949,"id":"Q389949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$CFBE1D65-CA36-4DB6-B39E-2D1C67F7A531","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"c3272cf56d677ead142c51427436a1eb1e09ed1e","datavalue":{"value":"Q127019226","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$8B908BC0-608C-4DFF-95CF-0D2D459E6A8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8e64a4d69f423533fbb4bdaa6f036b3264960def","datavalue":{"value":"10.7151/DMGT.2244","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2062677$186A3738-7FE8-42EE-BA11-545201A41693","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"836368b6337657a52f201de441b98aececc2523a","datavalue":{"value":{"entity-type":"item","numeric-id":2725179,"id":"Q2725179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$4DDFB774-5B84-4FD3-87DE-E58BA933A6CA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b046708db6fbde0dbe914c65525f44ca03042441","datavalue":{"value":{"entity-type":"item","numeric-id":3111664,"id":"Q3111664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"deceb9e73c1e3aa2adb0957ef8db37029b85bd2c","datavalue":{"value":{"amount":"+0.8093153238296509","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":"Q2062677$BBD87B8F-0D7A-4362-B653-A055155FFE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46d524c697fd414b106cb5b5a16082a7071a8532","datavalue":{"value":{"entity-type":"item","numeric-id":389949,"id":"Q389949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"acf8213b51288bfebe5b701d98aa5f19e9bfd52a","datavalue":{"value":{"amount":"+0.8005169034004211","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":"Q2062677$12AAA9B5-6F2C-4D0D-A23C-3D221455B359","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78c764b94d69a53b2baaa80478786c8c2564e6a9","datavalue":{"value":{"entity-type":"item","numeric-id":692888,"id":"Q692888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54baceabf988bb7140c9739018d1fc96a2bf0892","datavalue":{"value":{"amount":"+0.7985212802886963","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":"Q2062677$782569D3-272F-4583-9CD9-EF09E34B273F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1b86d4d2d33c372163b76e7a82c4c1d9955d89f6","datavalue":{"value":{"entity-type":"item","numeric-id":3569897,"id":"Q3569897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ee8bd7f41f553753437c100256916fbf9a48e2a5","datavalue":{"value":{"amount":"+0.7939321994781494","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":"Q2062677$D1478B67-83B9-421F-AB09-392F9B570265","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e6bdaa5285a2245defa2f43214bfd0a75a1c2264","datavalue":{"value":{"entity-type":"item","numeric-id":3596729,"id":"Q3596729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"045c9d645721851c7d725c588a425d279368f93c","datavalue":{"value":{"amount":"+0.7923237085342407","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":"Q2062677$0B33D582-832D-4CAF-B011-D2EA562358F2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6e2260e47a2889770c9d5516a7c5ae827b188d2b","datavalue":{"value":{"entity-type":"item","numeric-id":6830563,"id":"Q6830563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2062677$779740ED-57F6-42CC-8200-928194473C4C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2062677","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2062677"}}}}}