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