Centroidal Localization Game

Bartłomiej Bosek , Przemysław Gordinowicz , Jarosław Grytczuk , Nicolas Nisse , Joanna Chybowska-Sokół , Małgorzata Śleszyńska-Nowak

Abstract

Rozważamy rozgrywany wariant parametru grafu zwanego centroidal dimention. Głównym wynikiem pracy jest twierdzenie o rozgrywanym wymiarze centroidalnym w grafach zewnętrznętrznie planarnych. Ograniczamy również wspomniany parametr przez szerokość ścieżkową oraz dowodzimy, że jego wyznaczenie jest problemem NP-trudnym.
Author Bartłomiej Bosek
Bartłomiej Bosek,,
-
, Przemysław Gordinowicz
Przemysław Gordinowicz,,
-
, Jarosław Grytczuk (FMIS / DAC)
Jarosław Grytczuk,,
- Department of Algebra and Combinatorics
, Nicolas Nisse
Nicolas Nisse,,
-
, Joanna Chybowska-Sokół (FMIS)
Joanna Chybowska-Sokół,,
- Faculty of Mathematics and Information Science
, Małgorzata Śleszyńska-Nowak (FMIS / DIPS)
Małgorzata Śleszyńska-Nowak,,
- Department of Information Processing Systems
Journal seriesElectronic Journal of Combinatorics, ISSN 1077-8926, (A 25 pkt)
Issue year2018
Vol25
No4
Pages1-19
Publication size in sheets0.9
Keywords in PolishPolicjanci i złodzieje, przeszukiwanie grafu, grafy zewnętrznieplanarne
Keywords in EnglishCops and robber, Graph searching, Outerplanar graphs
ASJC Classification1703 Computational Theory and Mathematics; 2608 Geometry and Topology; 2614 Theoretical Computer Science
URL https://testing.combinatorics.org/ojs/index.php/eljc/article/view/v25i4p62
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 25.0, 04-02-2019, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 04-02-2019, ArticleFromJournal
Publication indicators Scopus SNIP (Source Normalised Impact per Paper): 2017 = 1.06; WoS Impact Factor: 2017 = 0.762 (2) - 2017=0.759 (5)
Citation count*
Cite
Share Share

Get link to the record


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back