3 papers
math.CO2020
Scale-free spanning trees: complexity, bounds and algorithms
Yury Orlovich, Kirill Kukharenko, Volker Kaibel +1
We introduce and study the general problem of finding a most "scale-free-like" spanning tree of a connected graph. It is motivated by a particular problem in epidemiology, and may…
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…