Network search games, with arbitrary searcher starting point

被引：26

作者：

Dagan, Arnon ^{[2
]}

Gal, Shmuel ^{[1
]}

机构：

[1] Univ Haifa, Dept Stat, IL-31905 Haifa, Israel

[2] Univ Haifa, Dept Comp Sci, IL-31905 Haifa, Israel

来源：

NETWORKS | 2008年 / 52卷 / 03期

关键词：

search games; network search; star search; Chinese postman; weakly Eulerian; absolute center;

D O I：

10.1002/net.20241

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We analyze a zero-sum game between a blind unit-speed searcher and a stationary hider on a given network Q, where the payoff is the time for the searcher to reach the hider. In contrast to the standard game studied in the literature, we do not assume that the searcher has to start from a fixed point (known to the hider) but can choose his starting point. We show that for some networks, including trees, the optimal searcher, and hider strategies have a simple structure. (C) 2008 Wiley Periodicals, Inc.

引用

页码：156 / 161

页数：6

共 20 条

[1]

Alpern S, 1974, DIFFERENTIAL GAMES C, P181

[2]

Alpern S., 2003, KLUWER INT SERIES OP

[3]

ALPERN S, 2005, CDAM200515 LOND SCH

[4]

BENKOSKI SJ, 1991, NAV RES LOG, V38, P469, DOI 10.1002/1520-6750(199108)38:4<469::AID-NAV3220380404>3.0.CO

[5]

2-E

[6]

DAGAN A, 2005, THESIS U HAIFA HAIFA

[7] The absolute center of a network [J].

Dvir, D ;

Handler, GY .

NETWORKS, 2004, 43 (02) :109-118

[8]

Gal S, 2000, INT J GAME THEORY, V29, P533

[9]

Gal S., 1980, SEARCH GAMES

[10]

Gal S., 1990, PROBAB ENG INF SCI, V4, P311, DOI [10.1017/S0269964800001625, DOI 10.1017/S0269964800001625]

← 1 2 →