صورت های الگوریتمی گراف های رومن

فرض کنید (E, V = (G یک گراف است. مجموعه ی V ⊆ S را یک مجموعه احاطه گر G می نامیم اگر هر راس در S \ V مجاور به حداقل یک راس در S است. عدد احاطه گر G برابر با کمترین اندازه یک مجموعه احاطه گر G است که آن را با (G γ نمایش می دهیم. یک تابع احاطه گر رومن (RDF) برای G تابع {2, 1, 0 → {V : f است به طوری که هر راس V ∈ v با 0) = v (f مجاور به یک ∑ = (V(f است. کمترین وزن یک RDF v∈V f(v) با برابر f وزن. است f(u) = 2 با u راس برای G را عدد احاطه گری رومن G می نامیم و آن را با (G (γR نمایش می دهیم. گراف G را یک گراف رومن می نامیم اگر (G (2γ) = G (γR. در این مقاله ابتدا نشان می دهیم که مسئله تصمیم گیری در مورد اینکه یک گراف رومن است یک مسئله hard-NP است. سپس یک الگوریتم زمان خطی ارایه می کنیم که تصمیم می گیرد یک گراف تک دور یک گراف رومن است.