کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6871133 | 1440178 | 2018 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Recognition and characterization of unit interval graphs with integer endpoints
ترجمه فارسی عنوان
شناسایی و مشخص نمودن نمودارهای واحدی واحد با انتهای عدد صحیح
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
نمودار فاصله واحد زیرگفتار منجر به ممنوعیت نمودار فاصله مناسب،
ترجمه چکیده
ما این نمودارهای واحد را با یک مدل با فواصل نقطه انتهایی عدد و طول تجویز شده بررسی می کنیم. ما یک نتیجه ساختاری برای این زیرمجموعه گراف داریم که منجر به الگوریتم تشخیص زمان دوم می شود، به عنوان گواهی مثبت یک مدل از حداقل طول کل و به عنوان گواهی منفی یک زیرگراف القا شده ممنوع است. ما همچنین یک الگوریتم زمان محوری را برای ساختن، با توجه به یک نمودار بازه واحد، یک مدل بازه واحد با نقطه انتهایی عددی ارائه می دهیم که طول فاصله را به حداقل ممکن است.
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We study those unit interval graphs having a model with intervals of integer endpoints and prescribed length. We present a structural result for this graph subclass which leads to a quadratic-time recognition algorithm, giving as positive certificate a model of minimum total length and as negative certificate a forbidden induced subgraph. We also present a quadratic-time algorithm to build, given a unit interval graph, a unit interval model with integer endpoints for which the interval length is as minimum as possible.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 168-176
Journal: Discrete Applied Mathematics - Volume 245, 20 August 2018, Pages 168-176
نویسندگان
G. Durán, F. Fernández Slezak, L.N. Grippo, F.de S. Oliveira, J.L. Szwarcfiter,