Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual

DOI10.1007/11847250_19MaRDI QIDQ3499738zbMATH OpenOpenAlexFDO

Authors Jiong Guo, Rolf Niedermeier, Sebastian Wernicke

Publication date 3 June 2008

Published in Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11847250_19

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fixed-parameter tractability results for full-degree spanning tree and its dual
• On the directed full degree spanning tree problem
• scientific article; zbMATH DE number 1563034
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Algorithms and Data Structures

Cited in

(9)

• The parameterized complexity of the induced matching problem
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• Bidimensionality and kernels
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Fixed-Parameter Tractability for Non-Crossing Spanning Trees
• Kernelization: new upper and lower bound techniques
• On the directed full degree spanning tree problem
• A Retrospective on (Meta) Kernelization
• A linear kernel for a planar connected dominating set

This page was built for publication: Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499738)