فا   |   En
Login
مشاهده‌ مشخصات مقاله

یک حد پایین برای یافتن یک پوشش هندسی برای یک گراف هندسی نادقیق

Authors
  • ابوالفضل پورعیدی
  • محمد فرشی
Conference بیست و یکمین کنفرانس ملی سالانه انجمن کامپیوتر
Abstract یک -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 سخت است.
قیمت
  • برای اعضای سایت : 100,000 Rial
  • برای دانشجویان عضو انجمن : 20,000 Rial
  • برای اعضای عادی انجمن : 40,000 Rial

خرید مقاله