@inproceedings{be7370437dc14032b07e7a6effbefff0,
title = "The complexity of algorithms computing game trees on random assignments",
abstract = "The complexity of algorithms for computing game trees on random assignments has been given substantial attention in the literature. In this line, we investigate the complexity of algorithms that compute a special class of game trees T2k from a new perspective -eigen-distribution. This particular distribution is defined as the worst distribution on assignments to variables of T2k regarding a best algorithm. In this paper, we show the eigen-distribution on assignments for T2 k in two separate cases, where the assignments to leaves are independently distributed (ID) and correlated distributed(CD). Then we use eigen-distribution to derive the tight bound of the complexity of algorithms for T2*.",
author = "Liu, \{Chen Guang\} and Kazuyuki Tanaka",
year = "2007",
doi = "10.1007/978-3-540-72870-2\_23",
language = "英语",
isbn = "9783540728689",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "241--250",
booktitle = "Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings",
note = "3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007 ; Conference date: 06-06-2007 Through 08-06-2007",
}