کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4950586 | 1440713 | 2017 | 16 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Exact algorithms for Maximum Induced Matching
ترجمه فارسی عنوان
الگوریتم های دقیق برای حداکثر تطبیق القایی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
الگوریتم های دقیق الگوریتم های گراف، حداکثر تطبیق القایی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in Oâ(1.4231n) time and polynomial space or Oâ(1.3752n) time and exponential space.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information and Computation - Volume 256, October 2017, Pages 196-211
Journal: Information and Computation - Volume 256, October 2017, Pages 196-211
نویسندگان
Mingyu Xiao, Huan Tan,