Fixed‐parameter tractability results for full‐degree spanning tree and its dual | Zendy

Guo Jiong | Zendy; Niedermeier Rolf | Zendy; Wernicke Sebastian | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Premium

Fixed‐parameter tractability results for full‐degree spanning tree and its dual

Author(s) -

Guo Jiong,

Niedermeier Rolf,

Wernicke Sebastian

Publication year - 2010

Publication title -

networks

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.977

H-Index - 64

eISSN - 1097-0037

pISSN - 0028-3045

DOI - 10.1002/net.20353

Subject(s) - spanning tree , combinatorics , mathematics , treewidth , degree (music) , minimum degree spanning tree , vertex (graph theory) , minimum spanning tree , feedback vertex set , parameterized complexity , independent set , bounded function , graph , discrete mathematics , pathwidth , line graph , mathematical analysis , physics , acoustics

We provide first‐time fixed‐parameter tractability results for the NP‐hard problems M AXIMUM F ULL ‐D EGREE S PANNING T REE (FDST) and M INIMUM ‐V ERTEX F EEDBACK E DGE S ET . These problems are dual to each other. In M AXIMUM FDST, the task is to find a spanning tree for a given graph that maximizes the number of vertices that preserve their degree. For M INIMUM ‐V ERTEX F EEDBACK E DGE S ET , the task is to minimize the number of vertices that end up with a reduced degree. Parameterized by the solution size, we exhibit that M INIMUM ‐V ERTEX F EEDBACK E DGE S ET is fixed‐parameter tractable and has a problem kernel with the number of vertices linearly depending on the parameter k . Our main contribution for M AXIMUM F ULL ‐D EGREE S PANNING T REE , which is W[1]‐hard, is a linear‐size problem kernel when restricted to planar graphs. Moreover, we present a dynamic programing algorithm for graphs of bounded treewidth. © 2009 Wiley Periodicals, Inc. NETWORKS, 2010

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here

Accelerating Research