کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7543456 | 1489487 | 2018 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Linear-time recognition of map graphs with outerplanar witness
ترجمه فارسی عنوان
تشخیص خطی زمانی از نمودار نقشه با شاهد بیرونی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودارهای پلانار، نمودار نقشه ها، الگوریتم های گواهی،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
کنترل و بهینه سازی
چکیده انگلیسی
We give a new and purely combinatorial algorithm that decides whether a graph G is a map graph having an outerplanar witness W. This is a step towards a first combinatorial recognition algorithm for general map graphs. The algorithm runs in time and space O(n+m). In contrast to Thorup's approach, it computes the witness graph W in the affirmative case.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Optimization - Volume 28, May 2018, Pages 63-77
Journal: Discrete Optimization - Volume 28, May 2018, Pages 63-77
نویسندگان
Matthias Mnich, Ignaz Rutter, Jens M. Schmidt,