Научные статьи
\
Математика. Естественные науки
\
Математика
\
Теория вероятностей и математическая статистика
О задаче приближенного нахождения максимальной двудольной клики
Автор: Кузюрин Н.Н.
Журнал: Труды Института системного программирования РАН @trudy-isp-ran
Статья в выпуске: 3 т.29, 2017 года.
Бесплатный доступ
Задача о нахождении большой "спрятанной" клики в случайном графе и ее аналог для двудольных графов являются объектами рассмотрения в данной заметке.
Случайный граф, большая спрятанная клика, сложность нахождения
Короткий адрес: https://sciup.org/14916436
IDR: 14916436 | DOI: 10.15514/ISPRAS-2017-29(3)-12
On the problem of finding approximation of bipatite cliques
In this paper, we consider the problem of finding large hidden clique in random graph and it’s analog for bipartite graphs.
Список литературы О задаче приближенного нахождения максимальной двудольной клики
- 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
- 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.
- R. Peters. The maximum edge biclique problem is NP-complete, Research Memorandum 789, Faculty of Economics and Business Administration, Tilburg University, 2000.
- 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.
- A. Juels, M. Peinado. Hiding Cliques for Cryptographic Security, Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 678-684.
- R. Karp. Reducibility among combinatorial problems, in The complexity of computer computations, Plenum Press, New York, 1972, pp. 85-103.
- 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.
- L. Kucera. Expected complexity of graph partitioning problems, Discrete Applied Mathematics, v. 57, 1995„ pp. 193-212.
- M. Jerrum. Large cliques elude the Metropolis process, Random Structures and Algorithms, v. 3, 1992, pp. 347-359.
- J. Hastad. Clique is hard to approximate within, Proceedings of the 37th Annual IEEE Symposium on Foundations of Computing, 1997, pp. 627-636.
- U. Feige, S. Kogan. Hardness of approximation of the balanced complete bipartite subgraph problem.
- 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.
- 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.
