RUS  ENG
Full version
JOURNALS // Proceedings of the Institute of Mathematics of the NAS of Belarus // Archive

Tr. Inst. Mat., 2012 Volume 20, Number 1, Pages 74–82 (Mi timb164)

Relaxation of the famous $NP$-complete polar graphs recognition problem leading to the fast polynomial-time algorithm

R. A. Petrovich

Belarusian State University, Minsk

Abstract: Considered the class of polar graphs and some of its subclasses. Graph $G=(V,E)$ is called polar if there exist a partition $VG=A\cup B$ of its vertex set such that all connected components of subgraphs $G(B)$ and $\overline{G(A)}$ are cliques.
It is known that the polar graph recognition problem is $NP$-complete.
In this paper the relaxation of the mentioned problem leading to the fast polynomial-time algorithm is proposed.

UDC: 519.1

Received: 13.02.2012



© Steklov Math. Inst. of RAS, 2025