کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
438100 690225 2008 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Matching cutsets in graphs of diameter 2
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Matching cutsets in graphs of diameter 2
چکیده انگلیسی

We say that a graph has a matching cutset if its vertices can be coloured in red and blue in such a way that there exists at least one vertex coloured in red and at least one vertex coloured in blue, and every vertex has at most one neighbour coloured in the opposite colour. In this paper we study the algorithmic complexity of a problem of recognizing graphs which possess a matching cutset. In particular we present a polynomial-time algorithm which solves this problem for graphs of diameter two.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 407, Issues 1–3, 6 November 2008, Pages 574-582