کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430024 687781 2014 23 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Parameterized complexity of connected even/odd subgraph problems
ترجمه فارسی عنوان
پیچیدگی پارامترهای مشکلات مرتبط با زیرگراف حتی / متناوب
کلمات کلیدی
پیچیدگی پارامتریک، گراف اویلر، حتی گراف، نمودار عجیب، درخت عرض
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• The k-Edge Connected Odd Subgraph problem is FPT when parameterized by k.
• The k  -Vertex Eulerian Subgraph problem is W[1]W[1]-hard when parameterized by k.
• The treewidth of minimal connected odd graphs with even number of edges is at most three.

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about:
• a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and
• a connected k-vertex induced subgraph with all vertices of even degrees, the problem known as k-Vertex Eulerian Subgraph. We show that k-Edge Connected Odd Subgraph is FPT and k-Vertex Eulerian Subgraph is W[1]W[1]-hard. Our FPT algorithm is based on a novel combinatorial result on the treewidth of minimal connected odd graphs with even amount of edges.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 80, Issue 1, February 2014, Pages 157–179
نویسندگان
, ,