Centroidal localization game

2018
journal article
article
dc.abstract.enOne 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 {v1,⋯,vk} such that the vector (d1,⋯,dk) of the distances d(vi,r) between the detectors and the entity's location r allows to uniquely determine r for every r∈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 {v1,⋯,vk}, we get only relative distances between the moving entity's location r and the devices (roughly, for every 1≤i,j≤k, it is provided whether d(vi,r)>, <, or = to d(vj,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.pl
dc.affiliationWydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznejpl
dc.contributor.authorBosek, Bartłomiej - 114402 pl
dc.contributor.authorGordinowicz, Przemysławpl
dc.contributor.authorGrytczuk, Jarosław - 128201 pl
dc.contributor.authorNisse, Nicolaspl
dc.contributor.authorSokół, Joannapl
dc.contributor.authorŚleszyńska-Nowak, Małgorzatapl
dc.date.accession2019-04-11pl
dc.date.accessioned2019-05-09T09:49:16Z
dc.date.available2019-05-09T09:49:16Z
dc.date.issued2018pl
dc.date.openaccess0
dc.description.accesstimew momencie opublikowania
dc.description.number4pl
dc.description.versionostateczna wersja wydawcy
dc.description.volume25pl
dc.identifier.articleidP4.62pl
dc.identifier.eissn1077-8926pl
dc.identifier.issn1097-1440pl
dc.identifier.projectPBS2/B3/24/2014pl
dc.identifier.projectROD UJ / OPpl
dc.identifier.urihttps://ruj.uj.edu.pl/xmlui/handle/item/74297
dc.identifier.weblinkhttps://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p62pl
dc.languageengpl
dc.language.containerengpl
dc.rightsUdzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa*
dc.rights.licenceCC-BY-ND
dc.rights.urihttp://creativecommons.org/licenses/by-nd/4.0/legalcode.pl*
dc.share.typeotwarte czasopismo
dc.subject.encops and robberpl
dc.subject.engraph searchinpl
dc.subject.enouterplanar graphspl
dc.subtypeArticlepl
dc.titleCentroidal localization gamepl
dc.title.journalThe Electronic Journal of Combinatoricspl
dc.typeJournalArticlepl
dspace.entity.typePublication
dc.abstract.enpl
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 {v1,⋯,vk} such that the vector (d1,⋯,dk) of the distances d(vi,r) between the detectors and the entity's location r allows to uniquely determine r for every r∈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 {v1,⋯,vk}, we get only relative distances between the moving entity's location r and the devices (roughly, for every 1≤i,j≤k, it is provided whether d(vi,r)>, <, or = to d(vj,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.
dc.affiliationpl
Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
dc.contributor.authorpl
Bosek, Bartłomiej - 114402
dc.contributor.authorpl
Gordinowicz, Przemysław
dc.contributor.authorpl
Grytczuk, Jarosław - 128201
dc.contributor.authorpl
Nisse, Nicolas
dc.contributor.authorpl
Sokół, Joanna
dc.contributor.authorpl
Śleszyńska-Nowak, Małgorzata
dc.date.accessionpl
2019-04-11
dc.date.accessioned
2019-05-09T09:49:16Z
dc.date.available
2019-05-09T09:49:16Z
dc.date.issuedpl
2018
dc.date.openaccess
0
dc.description.accesstime
w momencie opublikowania
dc.description.numberpl
4
dc.description.version
ostateczna wersja wydawcy
dc.description.volumepl
25
dc.identifier.articleidpl
P4.62
dc.identifier.eissnpl
1077-8926
dc.identifier.issnpl
1097-1440
dc.identifier.projectpl
PBS2/B3/24/2014
dc.identifier.projectpl
ROD UJ / OP
dc.identifier.uri
https://ruj.uj.edu.pl/xmlui/handle/item/74297
dc.identifier.weblinkpl
https://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p62
dc.languagepl
eng
dc.language.containerpl
eng
dc.rights*
Udzielam licencji. Uznanie autorstwa - Bez utworów zależnych 4.0 Międzynarodowa
dc.rights.licence
CC-BY-ND
dc.rights.uri*
http://creativecommons.org/licenses/by-nd/4.0/legalcode.pl
dc.share.type
otwarte czasopismo
dc.subject.enpl
cops and robber
dc.subject.enpl
graph searchin
dc.subject.enpl
outerplanar graphs
dc.subtypepl
Article
dc.titlepl
Centroidal localization game
dc.title.journalpl
The Electronic Journal of Combinatorics
dc.typepl
JournalArticle
dspace.entity.type
Publication
Affiliations

* The migration of download and view statistics prior to the date of April 8, 2024 is in progress.

Views
0
Views per month
Downloads
bosek_et-al_centroidal_localization_game_2018.pdf
2