Tính nhạy cảm thông tin trong việc tính toán phân tán với lời khuyên: Tô màu đồ thị

Alon N., Babai L., Itai A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7(4), 567–583 (1986) Awerbuch, B., Goldberg, A., Luby, M., Plotkin, S.: Network decomposition and locality in distributed computation. In: 30th Symp. on Foundations of Computer Science (FOCS), pp. 364–369, (1989) Bellare M., Goldreich O., Sudan M.: Free bits, PCPs, and nonapproximability—towards tight results. SIAM J. Comput. 27(3), 804–915 (1998) Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. In: 32nd Int. Colloquium on Automata, Languages and Programming (ICALP), LNCS 3580, pp. 335–346 (2005) Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Labeling schemes for tree representation. In: 7th Int. Workshop on Distributed Computing (IWDC), LNCS 3741, pp. 13–24 (2005) Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. In: 18th ACM Symp. on Theory of Computing (STOC), pp. 206–219 (1986) Feige U., Kilian J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187–199 (1998) Fich F., Ruppert E.: Hundreds of impossibility results for distributed computing. Distrib. Comput. 16, 121–163 (2003) Fraigniaud, P., Ilcinkas, D., Pelc, A.: Oracle size: a new measure of difficulty for communication tasks. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 179–187 (2006) Fraigniaud, P., Ilcinkas, D., Pelc, A.: Tree exploration with an oracle. In: 31st Int. Symp. on Mathematical Foundations of Computer Science (MFCS), LNCS 4162, Springer, pp. 24–37 (2006) Fraigniaud, P., Korman, A., Lebhar, E.: Local MST computation with short advice. In: 19th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2007) Goldberg, A., Plotkin, S.: Efficient parallel algorithms for (Δ + 1)-coloring and maximal independent set problems. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315–324 (1987) Goldberg, A., Plotkin, S., Shannon, G.: Parallel symmetry-breaking in sparse graphs. In: 19th ACM Symp. on Theory of Computing (STOC), pp. 315–324 (1987) Karp, R.: Reducibility Among Combinatorial Problems. In: Complexity of Computer Computations, pp. 85–103 (1972) Kothapalli, K., Onus, M., Scheideler, C., Schindelhauer, C.: Distributed coloring in \({O(\sqrt{\log n})}\) bit rounds. In: 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2006) Kuhn, F., Moscibroda, T., Wattenhofer, R.: What cannot be computed Locally! In: 23th ACM Symp. on Principles of Distributed Computing, (PODC), pp. 300–309 (2004) Kuhn, F., Wattenhofer, R.: On the complexity of distributed graph coloring. In: 25th ACM Symp. on Principles of Distributed Computing (PODC), pp. 7–15 (2006) Linial N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193–201 (1992) Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036–1053 (1986) Lynch, N.: A hundred impossibility proofs for distributed computing. In: 8th ACM Symp. on Principles of Distributed Computing (PODC), pp. 1–28 (1989) Moscibroda, T., Wattenhofer, R.: Coloring unstructured radio networks. In: 17th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA), pp. 39–48 (2005) Naor M.: A lower bound on probabilistic algorithms for distributive ring coloring. SIAM J. Discrete Math. 4(3), 409–412 (1991) Naor, M., Stockmeyer, L.: What can be computed locally? In: 25th ACM Symposium on Theory of Computing (STOC), pp. 184–193 (1993) Nisse, N., Soguet, D.: Graph searching with advice. In: 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO), June 2007 Panconesi A., Rizzi R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14, 97–100 (2001) Panconesi, A., Srinivasan, A.: Improved distributed algorithms for coloring and network decomposition problems. In: 24th ACM Symp. on Theory of Computing (STOC), pp. 581–592 (1992) Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356–374 (1996) Peleg, D.: Distributed computing: a locality-sensitive approach. SIAM Monographs on Discrete Mathematics and applications. Philadelphia, PA (2000)