مشاهده مشخصات مقاله
یک حد پایین برای یافتن یک پوشش هندسی برای یک گراف هندسی نادقیق
|
نویسنده (ها) |
-
ابوالفضل پورعیدی
-
محمد فرشی
|
|
مربوط به کنفرانس |
بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر |
|
چکیده |
یک -t پوشش هندسی (1<t) برای گراف هم‌بند هندسی G، زیرگراف پوشای G' برای G است؛ به طوری که فاصله‌ی بین هر جفت از راس‌ها در G'، حداکثر t برابر فاصله‌‌شان در G است.
یک مجموعه نقطه نادقیق D، با دیسک‌هایی دوبه‌دو جدا از هم در صفحه مدل می‌شود. اگر از هر دیسک D یک نقطه انتخاب شود؛ آن‌گاه مجموعه‌ی حاصل یک نمونه‌ی دقیق از D است. گراف G=(D,E) برای مجموعه نقطه نادقیق D، یک گراف هندسی نادقیق است؛ که E یک مجموعه از جفت‌دیسک‌های نامرتب در D است. برای نمونه‌ی دقیق S از D، گراف G_S=(S,E_S) نمونه‌ی دقیق G متناظر با S است؛ که E_S مجموعه یال‌های E متناظر با S است.
در این مقاله نشان می‌دهیم که برای یک گراف هندسی نادقیق G=(D,E)، یافتن نمونه دقیق S از D به طوری که G_S=(S,E_S) شامل یک -tپوشش با حداکثر m یال است، یک مسئله‌ی -NP سخت است. |
|
قیمت |
-
برای اعضای سایت : ۱٠٠,٠٠٠ ریال
-
برای دانشجویان عضو انجمن : ۲٠,٠٠٠ ریال
-
برای اعضای عادی انجمن : ۴٠,٠٠٠ ریال
|
خرید مقاله
|
|
.gif){kind=icon}