The Game of Overprescribed Cops and Robbers Played on Graphs View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2017-07

AUTHORS

Anthony Bonato, Xavier Pérez-Giménez, Paweł Prałat, Benjamin Reiniger

ABSTRACT

We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered. More... »

PAGES

801-815

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00373-017-1815-2

DOI

http://dx.doi.org/10.1007/s00373-017-1815-2

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1085738707


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0104", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Statistics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Ryerson University", 
          "id": "https://www.grid.ac/institutes/grid.68312.3e", 
          "name": [
            "Department of Mathematics, Ryerson University, Toronto, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bonato", 
        "givenName": "Anthony", 
        "id": "sg:person.010371120002.33", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010371120002.33"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Nebraska\u2013Lincoln", 
          "id": "https://www.grid.ac/institutes/grid.24434.35", 
          "name": [
            "Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "P\u00e9rez-Gim\u00e9nez", 
        "givenName": "Xavier", 
        "id": "sg:person.015570001347.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015570001347.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Fields Institute for Research in Mathematical Sciences", 
          "id": "https://www.grid.ac/institutes/grid.249304.8", 
          "name": [
            "Department of Mathematics, Ryerson University, Toronto, ON, Canada", 
            "The Fields Institute for Research in Mathematical Sciences, Toronto, ON, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Pra\u0142at", 
        "givenName": "Pawe\u0142", 
        "id": "sg:person.01202024074.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01202024074.01"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Illinois Institute of Technology", 
          "id": "https://www.grid.ac/institutes/grid.62813.3e", 
          "name": [
            "Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Reiniger", 
        "givenName": "Benjamin", 
        "id": "sg:person.015636114547.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015636114547.07"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1002/rsa.20587", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002454234"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0196-6774(84)90019-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009236880"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(87)90034-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010327640"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/aama.1993.1019", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019148456"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0012-365x(83)90160-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021809830"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2010.01.015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024393527"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/rsa.20338", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029504242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/rsa.20338", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029504242"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jctb.2012.10.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1031193463"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-04565-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039629325", 
          "https://doi.org/10.1007/978-3-662-04565-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-04565-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1039629325", 
          "https://doi.org/10.1007/978-3-662-04565-7"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2010.10.002", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044178636"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/15427951.2007.10129149", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044896315"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.disc.2008.04.004", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1045980143"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0166-218x(84)90073-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047824907"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539793250767", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062879833"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0895480191198768", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062882821"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1106884102", 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/9781118032718", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1106884102"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2017-07", 
    "datePublishedReg": "2017-07-01", 
    "description": "We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00373-017-1815-2", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136071", 
        "issn": [
          "0911-0119", 
          "1435-5914"
        ], 
        "name": "Graphs and Combinatorics", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "4", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "33"
      }
    ], 
    "name": "The Game of Overprescribed Cops and Robbers Played on Graphs", 
    "pagination": "801-815", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "eab06cf0153b532a41902fc562b16f322ac5fa771264022d50f01dd048e9185d"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00373-017-1815-2"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1085738707"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00373-017-1815-2", 
      "https://app.dimensions.ai/details/publication/pub.1085738707"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T12:38", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000363_0000000363/records_70040_00000002.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00373-017-1815-2"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00373-017-1815-2'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00373-017-1815-2'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00373-017-1815-2'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00373-017-1815-2'


 

This table displays all metadata directly associated to this object as RDF triples.

143 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00373-017-1815-2 schema:about anzsrc-for:01
2 anzsrc-for:0104
3 schema:author N0eaa02668d924bce8858311d66f6547b
4 schema:citation sg:pub.10.1007/978-3-662-04565-7
5 https://app.dimensions.ai/details/publication/pub.1106884102
6 https://doi.org/10.1002/9781118032718
7 https://doi.org/10.1002/rsa.20338
8 https://doi.org/10.1002/rsa.20587
9 https://doi.org/10.1006/aama.1993.1019
10 https://doi.org/10.1016/0012-365x(83)90160-7
11 https://doi.org/10.1016/0166-218x(84)90073-8
12 https://doi.org/10.1016/0166-218x(87)90034-5
13 https://doi.org/10.1016/0196-6774(84)90019-1
14 https://doi.org/10.1016/j.disc.2008.04.004
15 https://doi.org/10.1016/j.disc.2010.01.015
16 https://doi.org/10.1016/j.disc.2010.10.002
17 https://doi.org/10.1016/j.jctb.2012.10.002
18 https://doi.org/10.1080/15427951.2007.10129149
19 https://doi.org/10.1137/s0097539793250767
20 https://doi.org/10.1137/s0895480191198768
21 schema:datePublished 2017-07
22 schema:datePublishedReg 2017-07-01
23 schema:description We consider the effect on the length of the game of Cops and Robbers when more cops are added to the game play. In Overprescribed Cops and Robbers, as more cops are added, the capture time (the minimum length of the game assuming optimal play) monotonically decreases. We give the full range of capture times for any number of cops on trees, and classify the capture time for an asymptotic number of cops on grids, hypercubes, and binomial random graphs. The capture time of planar graphs with a number of cops at and far above the cop number is considered.
24 schema:genre research_article
25 schema:inLanguage en
26 schema:isAccessibleForFree true
27 schema:isPartOf N9f48b425a28a466197325c50e93c4214
28 Na4b9633f729d4a3987b485b8deb577fd
29 sg:journal.1136071
30 schema:name The Game of Overprescribed Cops and Robbers Played on Graphs
31 schema:pagination 801-815
32 schema:productId N3c295fd94dab4473ab6cafb71f69e95f
33 N98561043e8b645cf944f720fbf83b27e
34 Nb5da2acebaf34630a1ed6fbbfbee2f5a
35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1085738707
36 https://doi.org/10.1007/s00373-017-1815-2
37 schema:sdDatePublished 2019-04-11T12:38
38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
39 schema:sdPublisher Ne7fe02ad0a2348399bdce5fbd527aa01
40 schema:url https://link.springer.com/10.1007%2Fs00373-017-1815-2
41 sgo:license sg:explorer/license/
42 sgo:sdDataset articles
43 rdf:type schema:ScholarlyArticle
44 N0eaa02668d924bce8858311d66f6547b rdf:first sg:person.010371120002.33
45 rdf:rest Nac3388408b214625aa363b328e37124d
46 N3c295fd94dab4473ab6cafb71f69e95f schema:name dimensions_id
47 schema:value pub.1085738707
48 rdf:type schema:PropertyValue
49 N98561043e8b645cf944f720fbf83b27e schema:name readcube_id
50 schema:value eab06cf0153b532a41902fc562b16f322ac5fa771264022d50f01dd048e9185d
51 rdf:type schema:PropertyValue
52 N99adcf21944a49a2b496c1a448ce015b rdf:first sg:person.015636114547.07
53 rdf:rest rdf:nil
54 N9f48b425a28a466197325c50e93c4214 schema:issueNumber 4
55 rdf:type schema:PublicationIssue
56 Na4b9633f729d4a3987b485b8deb577fd schema:volumeNumber 33
57 rdf:type schema:PublicationVolume
58 Nac3388408b214625aa363b328e37124d rdf:first sg:person.015570001347.10
59 rdf:rest Nc6a6c690e44749c79560f167fad6f375
60 Nb5da2acebaf34630a1ed6fbbfbee2f5a schema:name doi
61 schema:value 10.1007/s00373-017-1815-2
62 rdf:type schema:PropertyValue
63 Nc6a6c690e44749c79560f167fad6f375 rdf:first sg:person.01202024074.01
64 rdf:rest N99adcf21944a49a2b496c1a448ce015b
65 Ne7fe02ad0a2348399bdce5fbd527aa01 schema:name Springer Nature - SN SciGraph project
66 rdf:type schema:Organization
67 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
68 schema:name Mathematical Sciences
69 rdf:type schema:DefinedTerm
70 anzsrc-for:0104 schema:inDefinedTermSet anzsrc-for:
71 schema:name Statistics
72 rdf:type schema:DefinedTerm
73 sg:journal.1136071 schema:issn 0911-0119
74 1435-5914
75 schema:name Graphs and Combinatorics
76 rdf:type schema:Periodical
77 sg:person.010371120002.33 schema:affiliation https://www.grid.ac/institutes/grid.68312.3e
78 schema:familyName Bonato
79 schema:givenName Anthony
80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010371120002.33
81 rdf:type schema:Person
82 sg:person.01202024074.01 schema:affiliation https://www.grid.ac/institutes/grid.249304.8
83 schema:familyName Prałat
84 schema:givenName Paweł
85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01202024074.01
86 rdf:type schema:Person
87 sg:person.015570001347.10 schema:affiliation https://www.grid.ac/institutes/grid.24434.35
88 schema:familyName Pérez-Giménez
89 schema:givenName Xavier
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015570001347.10
91 rdf:type schema:Person
92 sg:person.015636114547.07 schema:affiliation https://www.grid.ac/institutes/grid.62813.3e
93 schema:familyName Reiniger
94 schema:givenName Benjamin
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015636114547.07
96 rdf:type schema:Person
97 sg:pub.10.1007/978-3-662-04565-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039629325
98 https://doi.org/10.1007/978-3-662-04565-7
99 rdf:type schema:CreativeWork
100 https://app.dimensions.ai/details/publication/pub.1106884102 schema:CreativeWork
101 https://doi.org/10.1002/9781118032718 schema:sameAs https://app.dimensions.ai/details/publication/pub.1106884102
102 rdf:type schema:CreativeWork
103 https://doi.org/10.1002/rsa.20338 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029504242
104 rdf:type schema:CreativeWork
105 https://doi.org/10.1002/rsa.20587 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002454234
106 rdf:type schema:CreativeWork
107 https://doi.org/10.1006/aama.1993.1019 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019148456
108 rdf:type schema:CreativeWork
109 https://doi.org/10.1016/0012-365x(83)90160-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021809830
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1016/0166-218x(84)90073-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047824907
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/0166-218x(87)90034-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010327640
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1016/0196-6774(84)90019-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009236880
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1016/j.disc.2008.04.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045980143
118 rdf:type schema:CreativeWork
119 https://doi.org/10.1016/j.disc.2010.01.015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024393527
120 rdf:type schema:CreativeWork
121 https://doi.org/10.1016/j.disc.2010.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044178636
122 rdf:type schema:CreativeWork
123 https://doi.org/10.1016/j.jctb.2012.10.002 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031193463
124 rdf:type schema:CreativeWork
125 https://doi.org/10.1080/15427951.2007.10129149 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044896315
126 rdf:type schema:CreativeWork
127 https://doi.org/10.1137/s0097539793250767 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062879833
128 rdf:type schema:CreativeWork
129 https://doi.org/10.1137/s0895480191198768 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882821
130 rdf:type schema:CreativeWork
131 https://www.grid.ac/institutes/grid.24434.35 schema:alternateName University of Nebraska–Lincoln
132 schema:name Department of Mathematics, University of Nebraska-Lincoln, Lincoln, NE, USA
133 rdf:type schema:Organization
134 https://www.grid.ac/institutes/grid.249304.8 schema:alternateName Fields Institute for Research in Mathematical Sciences
135 schema:name Department of Mathematics, Ryerson University, Toronto, ON, Canada
136 The Fields Institute for Research in Mathematical Sciences, Toronto, ON, Canada
137 rdf:type schema:Organization
138 https://www.grid.ac/institutes/grid.62813.3e schema:alternateName Illinois Institute of Technology
139 schema:name Department of Applied Mathematics, Illinois Institute of Technology, Chicago, IL, USA
140 rdf:type schema:Organization
141 https://www.grid.ac/institutes/grid.68312.3e schema:alternateName Ryerson University
142 schema:name Department of Mathematics, Ryerson University, Toronto, ON, Canada
143 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...