کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648861 1342433 2010 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid
چکیده انگلیسی

Given an undirected graph G=(V,E)G=(V,E) with matching number ν(G)ν(G), a dd-blocker is a subset of edges BB such that ν((V,E∖B))≤ν(G)−dν((V,E∖B))≤ν(G)−d and a dd-transversal TT is a subset of edges such that every maximum matching MM has |M∩T|≥d|M∩T|≥d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum dd-transversals and minimum dd-blockers in the special cases where GG is a grid graph or a tree.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issue 1, 6 January 2010, Pages 132–146
نویسندگان
, , , , , ,