An efficient algorithm for Mixed domination on Generalized Series-Parallel Graphs
سال انتشار: 1397
نوع سند: مقاله ژورنالی
زبان: انگلیسی
مشاهده: 103
فایل این مقاله در 17 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
JR_ASYAZDT-5-1_002
تاریخ نمایه سازی: 15 دی 1401
چکیده مقاله:
A mixed dominating set S of a graph G=(V, E) is a subset of vertices and edges like S \subseteq V \cup E such that each element v\in (V \cup E) \setminus S is adjacent or incident to at least one element in S. The mixed domination number \gamma_m(G) of a graph G is the minimum cardinality among all mixed dominating sets in G. The problem of finding \gamma_{m}(G) is known to be NP-complete. In this paper, we present an explicit polynomial-time algorithm using the parse tree to construct a mixed dominating set of size \gamma_{m}(G) where G is a generalized series-parallel graph.
کلیدواژه ها:
نویسندگان
- -
Department of Computer Science, Yazd University, Yazd, Iran.
- -
Department of Computer Science, Yazd University, Yazd, Iran.
- -
Department of Computer Science, Vali-e-Asr University of Rafsanjan, Rafsanjan, Iran.
- -
Department of Computer Science, Yazd University, Yazd, Iran.
- -
Department of Computer Science, The University of Auckland, Auckland, New Zealand.
مراجع و منابع این مقاله:
لیست زیر مراجع و منابع استفاده شده در این مقاله را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود مقاله لینک شده اند :