Showing 2001Show all
3 papers · 1 filter
cs.DM2001
On a Special Case of the Generalized Neighbourhood Problem
V. Naidenko, Yu. Orlovich
For a given finite class of finite graphs H, a graph G is called a realization of H if the neighbourhood of its any vertex induces the subgraph isomorphic to a graph of H. We consi…
cs.CC2001
On some optimization problems for star-free graphs
V. G. Naidenko, Yu. L. Orlovich
It is shown that in star-free graphs the maximum independent set problem, the minimum dominating set problem and the minimum independent dominating set problem are approximable up…
cs.CC2001
Recursively Undecidable Properties of NP
V. G. Naidenko
We show that there cannot be any algorithm that for a given nondeterministic polynomial-time Turing machine determinates whether or not the language recognized by this machine belo…