کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
436821 690041 2007 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The induced matching and chain subgraph cover problems for convex bipartite graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
The induced matching and chain subgraph cover problems for convex bipartite graphs
چکیده انگلیسی

We present an O(n2)-time algorithm for computing a maximum cardinality induced matching and a minimum cardinality cover by chain subgraphs for convex bipartite graphs. This improves the previous time bound of O(m2).

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 381, Issues 1–3, 22 August 2007, Pages 260-265