Preview

Труды Института системного программирования РАН

Расширенный поиск

О задаче приближенного нахождения максимальной двудольной клики

https://doi.org/10.15514/ISPRAS-2017-29(3)-12

Аннотация

Задача о нахождении большой "спрятанной" клики в случайном графе и ее аналог для двудольных графов являются объектами рассмотрения в данной заметке.

Об авторе

Н. Н. Кузюрин
Интитут системного программирования РАН
Россия


Список литературы

1. S. Khot. Improved inapproximability results for maxclique, chromatic number and approximate graph coloring, Proceedings of the 42th Annual Symposium on Foundations of Computer Science, 2001, pp. 600–609

2. U. Feige. Relations between average case complexity and approximation complexity, Proceedings of the 34th Annual Symposium on the Theory of Computing, 2002, pp. 534–543.

3. R. Peters. The maximum edge biclique problem is NP-complete, Research Memorandum 789, Faculty of Economics and Business Administration, Tilburg University, 2000.

4. U. Feige, R. Krauthhgamer. Finding and sertifying a large hidden clique in a semi-random graph, Random Structures and Algorithms, v. 13, 1998, pp. 457-466.

5. A. Juels, M. Peinado. Hiding Cliques for Cryptographic Security, Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 678-684.

6. R. Karp. Reducibility among combinatorial problems, in The complexity of computer computations, Plenum Press, New York, 1972, pp. 85-103.

7. R. Karp. The probabilistic analysis of some combinatorial search algorithms, in Algorithms and Complexity: New directions and recent results, Academic Press, 1976, pp. 1-19.

8. L. Kucera. Expected complexity of graph partitioning problems, Discrete Applied Mathematics, v. 57, 1995„ pp. 193-212.

9. M. Jerrum. Large cliques elude the Metropolis process, Random Structures and Algorithms, v. 3, 1992, pp. 347-359.

10. J. Hastad. Clique is hard to approximate within , Proceedings of the 37th Annual IEEE Symposium on Foundations of Computing, 1997, pp. 627-636.

11. U. Feige, S. Kogan. Hardness of approximation of the balanced complete bipartite subgraph problem.

12. N. Alon, A. Andoni, T. Kaufman, K. Matulef, R. Rubinfeld, N. Xie. Testing k-wise and almost k-wise independence, Proc. Annual Symposium on the Theory of Computing, 2007, pp. 496–505.

13. N. Alon, M. Krivelevich, B. Sudakov. Finding a large hidden clique in a random graph, Random Structures and Algorithms, 1998, v. 13, pp. 457–466.


Рецензия

Для цитирования:


Кузюрин Н.Н. О задаче приближенного нахождения максимальной двудольной клики. Труды Института системного программирования РАН. 2017;29(3):225-232. https://doi.org/10.15514/ISPRAS-2017-29(3)-12

For citation:


Kuzyurin N.N. On the problem of finding approximation of bipatite cliques. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2017;29(3):225-232. (In Russ.) https://doi.org/10.15514/ISPRAS-2017-29(3)-12



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)