TY - CHAP
AU - Tophinke, Doris
ED - Bommes, Michael
ED - Noack, Christina
ED - Tophinke, Doris
ID - 18287
T2 - Sprache als Form. FS für Utz Maas
TI - Schreiben gegen die Regel – Formen und Funktionen orthografischer Abweichungen im Internet Relay Chat (IRC)
ER -
TY - CHAP
AU - Tophinke, Doris
ED - Drescher, Martina
ID - 18321
T2 - Textsorten im romanischen Sprachvergleich
TI - Texttypologie aus diachroner Sicht
ER -
TY - CONF
AB - We analyze a randomized pursuit-evasion game on graphs. This game is played by two players, a hunter and a rabbit. Let G be any connected, undirected graph with n nodes. The game is played in rounds and in each round both the hunter and the rabbit are located at a node of the graph. Between rounds both the hunter and the rabbit can stay at the current node or move to another node. The hunter is assumed to be restricted to the graph G: in every round, the hunter can move using at most one edge. For the rabbit we investigate two models: in one model the rabbit is restricted to the same graph as the hunter, and in the other model the rabbit is unrestricted, i.e., it can jump to an arbitrary node in every round.
We say that the rabbit is caught as soon as hunter and rabbit are located at the same node in a round. The goal of the hunter is to catch the rabbit in as few rounds as possible, whereas the rabbit aims to maximize the number of rounds until it is caught. Given a randomized hunter strategy for G, the escape length for that strategy is the worst case expected number of rounds it takes the hunter to catch the rabbit, where the worst case is with regards to all (possibly randomized) rabbit strategies. Our main result is a hunter strategy for general graphs with an escape length of only O
(n log (diam(G))) against restricted as well as unrestricted rabbits. This bound is close to optimal since Ω(n) is a trivial lower bound on the escape length in both models. Furthermore, we prove that our upper bound is optimal up to constant factors against unrestricted rabbits.
AU - Adler, Micah
AU - Räcke, Harald
AU - Sivadasan, Naveen
AU - Sohler, Christian
AU - Vöcking, Berthold
ID - 18566
SN - 0302-9743
T2 - Proceedings of the 29th International Colloquium on Automata, Languages and Programming
TI - Randomized Pursuit-Evasion in Graphs
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18756
T2 - Mathematical Reviews [MR 2002h:01005]
TI - Degnan, Michael J., “What is the Scope of Aristotle’s Defense of the PNC”, Apeiron 32 (1999), no. 3, 243–274
ER -
TY - GEN
AU - Peckhaus, Volker
ID - 18751
T2 - Mathematical Reviews [MR 2002h:01001]
TI - Thom, Paul, “The Principle of Non-contradiction in Early Greek Philosophy”, Apeiron 32 (1999), no. 3, 153–170
ER -
TY - JOUR
AU - Eke, Norbert Otto
ID - 19362
IS - Juli
JF - Text + Kritik, H. 155: Herta Müller
TI - Schönheit der Verwund(er)ung. Herta Müllers Weg zum Gedicht
ER -
TY - THES
AU - Sohler, Christian
ID - 18573
SN - 3-935433-28-X
TI - Property Testing and Geometry
ER -
TY - CONF
AU - Wanka, Rolf
ID - 19850
SN - 0302-9743
T2 - Proc. Workshop on Graph-Theoretic Concepts in Computer Science (WG)
TI - Any Load-Balancing Regimen for Evolving Tree Computations on Circulant Graphs Is Asymptotically Optimal
ER -
TY - CONF
AU - Brinkmann, André
AU - Salzwedel, Kay
AU - Scheideler, Christian
ID - 2136
T2 - SPAA
TI - Compact, adaptive placement schemes for non-uniform requirements
ER -
TY - JOUR
AU - de los Arcos, T.
AU - Vonau, F.
AU - Garnier, M. G.
AU - Thommen, V.
AU - Boyen, H.-G.
AU - Oelhafen, P.
AU - Düggelin, M.
AU - Mathis, D.
AU - Guggenheim, R.
ID - 22620
JF - Applied Physics Letters
SN - 0003-6951
TI - Influence of iron–silicon interaction on the growth of carbon nanotubes produced by chemical vapor deposition
ER -