|
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.
Received: 13.02.2012
Citation:
R. A. Petrovich, “Relaxation of the famous $NP$-complete polar graphs recognition problem leading to the fast polynomial-time algorithm”, Tr. Inst. Mat., 20:1 (2012), 74–82
Linking options:
https://www.mathnet.ru/eng/timb164 https://www.mathnet.ru/eng/timb/v20/i1/p74
|
|