Parity games on undirected graphs

被引：0
作者：
Berwanger, Dietmar [2 ]
Serre, Olivier [1 ,2 ]
机构：
[1] Univ Paris 07, LIAFA, F-75221 Paris 05, France
[2] CNRS, F-75700 Paris, France
来源：
INFORMATION PROCESSING LETTERS | 2012年 / 112卷 / 23期
关键词：
Algorithms; Parity games; Graph structure complexity; WIDTH;
D O I：
10.1016/j.ipl.2012.08.021
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We examine the complexity of solving parity games in the special case when the underlying game graph is undirected. For strictly alternating games, that is, when the game graph is bipartite between the players, we observe that the solution can be computed in linear time. In contrast, when the assumption of strict alternation is dropped, we show that the problem is as hard in the undirected case as it is in the general, directed, case. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码：928 / 932
页数：5
相关论文
共 12 条
  • [1] [Anonymous], 1991, Proc. 32nd IEEE Symp. Found, DOI DOI 10.1109/SFCS.1991.185392
  • [2] Belkhir W, 2007, LECT NOTES COMPUT SC, V4855, P508
  • [3] Berwanger D, 2006, LECT NOTES COMPUT SC, V3884, P524
  • [4] Berwanger D, 2005, LECT NOTES COMPUT SC, V3452, P209
  • [5] Fearnley J, 2012, LECT NOTES COMPUT SC, V7392, P189, DOI 10.1007/978-3-642-31585-5_20
  • [6] Gradel E., 2002, LECT NOTES COMPUTER, V2500
  • [7] Gurevich Y., 1982, P 14 ANN ACM S THEOR, P60, DOI DOI 10.1145/800070.802177
  • [8] Digraph measures: Kelly decompositions, games, and orderings
    Hunter, Paul
    Kreutzer, Stephan
    [J]. THEORETICAL COMPUTER SCIENCE, 2008, 399 (03) : 206 - 219
  • [9] A DETERMINISTIC SUBEXPONENTIAL ALGORITHM FOR SOLVING PARITY GAMES
    Jurdzinski, Marcin
    Paterson, Mike
    Zwick, Uri
    [J]. SIAM JOURNAL ON COMPUTING, 2008, 38 (04) : 1519 - 1532
  • [10] Obdrzálek J, 2003, LECT NOTES COMPUT SC, V2725, P80
12