کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
7543456 1489487 2018 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Linear-time recognition of map graphs with outerplanar witness
ترجمه فارسی عنوان
تشخیص خطی زمانی از نمودار نقشه با شاهد بیرونی
کلمات کلیدی
نمودارهای پلانار، نمودار نقشه ها، الگوریتم های گواهی،
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات کنترل و بهینه سازی
چکیده انگلیسی
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
نویسندگان
, , ,