On some optimization problems for star-free graphs

Simple item page
dc.creatorNaidenko, V. G.
dc.creatorOrlovich, Yu. L.
dc.date2001-06-25
dc.date.accessioned2026-07-07T03:17:17Z
dc.date.available2026-07-07T03:17:17Z
dc.descriptionIt 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 to constant factor by any maximal independent set.
dc.description6 pages, in Russian
dc.identifierhttps://arxiv.org/abs/cs/0106048
dc.identifierhttp://arxiv.org/abs/cs/0106048
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30664
dc.subjectComputational Complexity
dc.subjectDiscrete Mathematics
dc.subjectG.1.2; G.2.2
dc.titleOn some optimization problems for star-free graphs
dc.typetext

Files

Collections

arXiv