About: Catching a Fast Robber on Interval Graphs

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

About: Catching a Fast Robber on Interval 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
rdfs:seeAlso	http://dx.doi.org/10.1007/978-3-642-20877-5_35
Description	We analyse the Cops and oo-fast Robber game on the class of interval graphs and show it to be polynomially decidable on such graphs. This solves an open problem posed in paper %22Pursuing a fast robber on a graph%22 by Fomin et al. [4] The game is known to be already NP-hard on chordal graphs and split-graphs. The game is played by two players, one controlling k cops, the other a robber. The players alternate in turns, all the cops move at once to distance at most one, the robber moves along any cop-free path. Cops win by capturing the robber, the robber by avoiding capture. The analysis relies on the properties of an interval representation of the graph. We show that while the game-state graph is generally exponential, every cops'' move can be decomposed into simple moves of three types, and the states are reduced to those defined by certain cuts of the interval representation. This gives a restricted game equivalent to the original one together with a winning strategy computable in polynomial time. We analyse the Cops and oo-fast Robber game on the class of interval graphs and show it to be polynomially decidable on such graphs. This solves an open problem posed in paper %22Pursuing a fast robber on a graph%22 by Fomin et al. [4] The game is known to be already NP-hard on chordal graphs and split-graphs. The game is played by two players, one controlling k cops, the other a robber. The players alternate in turns, all the cops move at once to distance at most one, the robber moves along any cop-free path. Cops win by capturing the robber, the robber by avoiding capture. The analysis relies on the properties of an interval representation of the graph. We show that while the game-state graph is generally exponential, every cops'' move can be decomposed into simple moves of three types, and the states are reduced to those defined by certain cuts of the interval representation. This gives a restricted game equivalent to the original one together with a winning strategy computable in polynomial time. (en)
Title	Catching a Fast Robber on Interval Graphs Catching a Fast Robber on Interval Graphs (en)
skos:prefLabel	Catching a Fast Robber on Interval Graphs Catching a Fast Robber on Interval Graphs (en)
skos:notation	RIV/00216208:11320/11:10104228!RIV12-MSM-11320___
http://linked.open...avai/riv/aktivita	S Z
http://linked.open...avai/riv/aktivity	S, Z(MSM0021620838)
http://linked.open...iv/cisloPeriodika	1
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Gavenčiak, Tomáš
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
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	189295
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/11:10104228
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	interval graph representation; interval graph; combinatorial game; pursuit game; cop and robber game (en)
http://linked.open.../riv/klicoveSlovo	combinatorial game cop and robber game interval graph interval graph representation pursuit game
http://linked.open...odStatuVydavatele	DE - Spolková republika Německo
http://linked.open...ontrolniKodProRIV	[9B3D8D4A27BE]
http://linked.open...i/riv/nazevZdroje	Lecture Notes in Computer Science
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	1 (xsd:int)
http://linked.open...cetTvurcuVysledku	1 (xsd:int)
http://linked.open...UplatneniVysledku	2011
http://linked.open...v/svazekPeriodika	6648
http://linked.open...iv/tvurceVysledku	Gavenčiak, Tomáš
http://linked.open...n/vavai/riv/zamer	Moderní metody, struktury a systémy informatiky
issn	0302-9743
number of pages	12 (xsd:int)
http://bibframe.org/vocab/doi	10.1007/978-3-642-20877-5_35
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