کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8903522 1632569 2017 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A linear-time algorithm for the identifying code problem on block graphs
ترجمه فارسی عنوان
یک الگوریتم خطی زمان برای مشکل کد شناسایی در نمودار بلوک
کلمات کلیدی
کد شناسایی، بلوک نمودار، پیچیدگی محاسباتی،
ترجمه چکیده
مشکل کد شناسایی یک مشکل جستجوی خاص است که به صورت چالش برانگیزی از نظر نظری و از نقطه نظر محاسباتی حتی برای چندین نمودار که دیگر مشکلات سخت معمولا به راحتی حل می شود، مانند نمودارهای دو طرفه یا نمودارهای هوستر. از این رو، یک خط معمول برای حمله به این مشکل، تعیین حداقل کدهای شناسایی گراف های ویژه است. در این مقاله، مسئله تعیین توانایی حداقل کد شناسایی در نمودارهای بلوک (که نمودارهای هوستر بدون الماس) را بررسی می کنیم. ما یک الگوریتم خطی زمان برای این مشکل ارائه می دهیم، به عنوان یک تعمیم الگوریتم خطی زمانی پیشنهاد شده توسط آگر در سال 2010 برای مورد درختان. به این ترتیب، ما یک زیرمجموعه از نمودارهای هوستر ارائه می دهیم که برای آن کد خطای شناسایی می تواند در زمان خطی حل شود.
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش مقاله
یک الگوریتم خطی زمان برای مشکل کد شناسایی در نمودار بلوک
چکیده انگلیسی
The identifying code problem is a special search problem, challenging both from a theoretical and from a computational point of view, even for several graphs where other usually hard problems are easy to solve, like bipartite graphs or chordal graphs. Hence, a typical line of attack for this problem is to determine minimum identifying codes of special graphs. In this work we study the problem of determining the cardinality of a minimum identifying code in block graphs (that are diamond-free chordal graphs). We present a linear-time algorithm for this problem, as a generalization of a linear-time algorithm proposed by Auger in 2010 for the case of trees. Thereby, we provide a subclass of chordal graphs for which the identifying code problem can be solved in linear time.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 62, November 2017, Pages 249-254
نویسندگان
, , , ,