فهرست مقالات Maximal independent set

• دسترسی آزاد مقاله
  • صفحه چکیده
  • متن کامل
  
  1 - بهبود کران بالای عدد استقلال مجموعه مستقل ماکزیمال در گراف دیسک واحد
  غلام حسن شیردل مهدی جالینوسی
  10.30495/jnrm.2022.58031.2028
  در یک گراف دیسک واحد دو رأس مجاورند اگر با متر اقلیدسی دو بعدی فاصله بین آنها کوچکتر یا مساوی یک باشد. اندازه مجموعه مستقل ماکسیمال در یک گرافG را عدد استقلال گفته و با α(G) نشان می دهیم. اندازه مجموعه احاطه گر همبند مینیمال در گراف G را عدد احاطه گر همبند می گفته چکیده کامل

  در یک گراف دیسک واحد دو رأس مجاورند اگر با متر اقلیدسی دو بعدی فاصله بین آنها کوچکتر یا مساوی یک باشد. اندازه مجموعه مستقل ماکسیمال در یک گرافG را عدد استقلال گفته و با α(G) نشان می دهیم. اندازه مجموعه احاطه گر همبند مینیمال در گراف G را عدد احاطه گر همبند می گفته و با γ_c (G) نمایش می دهیم. واضح است اگر فاصله بین دو گره از یک گراف دیسک واحد بیشتر از یک باشد آن دو گره مسقل هستند. یک زیر مجموعه S از راس ها در یک گراف مجموعه احاطه گر نامیده می شود اگر هر راس از گراف G یا عضو مجموعه S باشد یا با عضوی از آن مجاور باشد. یک مجموعه احاطه گر همبند است اگر یک زیر گراف همبند القا کند. یک مجموعه احاطه گر همبند اغلب به عنوان یک دکل مجازی در شبکه های سنسور بی سیم جهت بهبود ارتباطات و کارایی یهتر استفاده می شود. واضح است که دکل مجازی کوچکتر کارایی بهتری دارد. با این حال محاسبه یک مجموعه احاطه گر همبند مینیمال همچنان NP-سخت است. از طرفی ارتباط بین اندازه مجموعه مستقل ماکسیمال و اندازه مجموعه احاطه گر همبند مینیمال در یک گراف G بسیار اهمیت دارد. هدف اصلی این مقاله بهبود بخشیدن به کران بالای عدد استقلال وابسته به عدد احاطه گر همبند برای یک گراف دیسک واحد است. بعلاوه ما کران بالای موجود تا کنون را بهبود داده ایم. پرونده مقاله