License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.29
URN: urn:nbn:de:0030-drops-99775
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9977/
Chen, Yen-Ting ;
Tsai, Meng-Tsung ;
Tsai, Shi-Chun
A Dichotomy Result for Cyclic-Order Traversing Games
Abstract
Traversing game is a two-person game played on a connected undirected simple graph with a source node and a destination node. A pebble is placed on the source node initially and then moves autonomously according to some rules. Alice is the player who wants to set up rules for each node to determine where to forward the pebble while the pebble reaches the node, so that the pebble can reach the destination node. Bob is the second player who tries to deter Alice's effort by removing edges. Given access to Alice's rules, Bob can remove as many edges as he likes, while retaining the source and destination nodes connected. Under the guide of Alice's rules, if the pebble arrives at the destination node, then we say Alice wins the traversing game; otherwise the pebble enters an endless loop without passing through the destination node, then Bob wins. We assume that Alice and Bob both play optimally.
We study the problem: When will Alice have a winning strategy? This actually models a routing recovery problem in Software Defined Networking in which some links may be broken. In this paper, we prove a dichotomy result for certain traversing games, called cyclic-order traversing games. We also give a linear-time algorithm to find the corresponding winning strategy, if one exists.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs:2018:9977,
author = {Yen-Ting Chen and Meng-Tsung Tsai and Shi-Chun Tsai},
title = {{A Dichotomy Result for Cyclic-Order Traversing Games}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {29:1--29:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9977},
URN = {urn:nbn:de:0030-drops-99775},
doi = {10.4230/LIPIcs.ISAAC.2018.29},
annote = {Keywords: st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network}
}
|
Keywords: |
|
st-planar graphs, biconnectivity, fault-tolerant routing algorithms, software defined network |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
