About: Cops and Robbers on Intersection Graphs

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Cops and Robbers on Intersection Graphs Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph G, one controlling k cops and the other one robber, all positioned on V G . The players alternate in moving their pieces to distance at most 1 each. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop-number of G, that is the smallest k such that k cops win the game, has recently been a widely studied parameter. Intersection graph classes are defined by their geometric representations: the vertices are represented by certain geometrical shapes and two vertices are adjacent if and only if their representations intersect. Some well-known intersection classes include interval and string graphs. Various properties of many of these classes have been studied recently, including an interest in their game-theoretic properties. In this paper we show an upper bound on the cop-number of string graphs and sharp bounds on the cop-number of interval filament graphs, circular graphs, circular arc graphs and function graphs. These results also imply polynomial algorithms determining cop-number for all these classes and their sub-classes. The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph G, one controlling k cops and the other one robber, all positioned on V G . The players alternate in moving their pieces to distance at most 1 each. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop-number of G, that is the smallest k such that k cops win the game, has recently been a widely studied parameter. Intersection graph classes are defined by their geometric representations: the vertices are represented by certain geometrical shapes and two vertices are adjacent if and only if their representations intersect. Some well-known intersection classes include interval and string graphs. Various properties of many of these classes have been studied recently, including an interest in their game-theoretic properties. In this paper we show an upper bound on the cop-number of string graphs and sharp bounds on the cop-number of interval filament graphs, circular graphs, circular arc graphs and function graphs. These results also imply polynomial algorithms determining cop-number for all these classes and their sub-classes. (en)
Title	Cops and Robbers on Intersection Graphs Cops and Robbers on Intersection Graphs (en)
skos:prefLabel	Cops and Robbers on Intersection Graphs Cops and Robbers on Intersection Graphs (en)
skos:notation	RIV/00216208:11320/13:10189961!RIV14-GA0-11320___
http://linked.open...avai/riv/aktivita	P S
http://linked.open...avai/riv/aktivity	P(GEGIG/11/E023), S
http://linked.open...vai/riv/dodaniDat	2014
http://linked.open...aciTvurceVysledku	Gavenčiak, Tomáš Jelínek, Vít Kratochvíl, Jan Klavík, Pavel
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	67075
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/13:10189961
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	games on graphs; pursuit games; cop and robber; interval filament graphs; string graphs; intersection graphs (en)
http://linked.open.../riv/klicoveSlovo	cop and robber games on graphs intersection graphs interval filament graphs pursuit games string graphs
http://linked.open...ontrolniKodProRIV	[89D5FE5DBA48]
http://linked.open...v/mistoKonaniAkce	Hong Kong
http://linked.open...i/riv/mistoVydani	Neuveden
http://linked.open...i/riv/nazevZdroje	Lecture Notes in Computer Science
http://linked.open...in/vavai/riv/obor	BA
http://linked.open...ichTvurcuVysledku	4 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Graph Drawings and Representations
http://linked.open...UplatneniVysledku	2013
http://linked.open...iv/tvurceVysledku	Gavenčiak, Tomáš Jelínek, Vít Kratochvíl, Jan Klavík, Pavel
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2013-12-16 (xsd:date)
issn	0302-9743
number of pages	11 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-45030-3_17
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-642-45029-7
http://localhost/t...ganizacniJednotka	11320

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software