Back to search

National and Kapodistrian University of Athens

Robbing, surfing and rioting games on graphs

Abstract

dc:description

Εστιάζουμε σε 3 διαφορετικά συνδυαστικά παιχνίδια καταδίωξης-αποφυγής. Για το διάσημο Αστυνόμοι & Κλέφτης (Cops & Robber), όπου αστυνόμοι-πιόνια προσπαθούν να αιχμαλωτίσουν έναν κλέφτη-πιόνι σε ένα γράφημα, μελετώνται 2 παραλλαγές. Αυτές είναι οι περιπτώσεις των κλασματικών αστυνόμων και του γρήγορου κλέφτη. Πέρα από κάποια γενικά αποτελέσματα, μελετώνται κυρίως τα γραφήματα τύπου πλέγματος. Για το παιχνίδι Επιτήρησης (Surveillance), που εισήχθη πρόσφατα με σκοπό τη μοντελοποίηση της προανάκλησης (prefetching) στον Ιστό, δίνεται ένα αποτέλεσμα δυσκολίας για γραφήματα με φραγμένο βαθμό. Σ'αυτό το παιχνίδι, ένας παρατηρητής προσπαθεί να προβλέψει κάθε πιθανή διαδρομή ενός σέρφερ. Επιπλέον, παρατίθεται μια γενικευμένη προσέγγιση Οφέλους-Ελλείμματος (Benefit-Deficit) ως εναλλακτικό πεδίο έρευνας. Τέλος, μελετάται η Αιώνια Κυριαρχία (Eternal Domination). Μια ομάδα φρουρών πρέπει να κυριαρχεί αιώνια πάνω σε ένα γράφημα και έτσι να προστατεύει ενάντια επιθέσεων σε οποιονδήποτε κόμβο. Λαμβάνονται υπόψη θέματα συνδυαστικής και πολυπλοκότητας.

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Λάμπρου Ιωάννης

Rights

Language dc:language
English

Identifiers

dc:identifier.*
Identifier
uoadl:1321357

Chain of custody

source
Harvested from
National and Kapodistrian University of Athens
Base URL
pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Λάμπρου Ιωάννης. Robbing, surfing and rioting games on graphs. 2014. https://pergamos.lib.uoa.gr/uoa/dl/object/1321357