On the directed full degree spanning tree problem

DOI10.1016/J.DISOPT.2010.09.001MaRDI QIDQ456701zbMATH OpenOpenAlexFDO

Authors Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh, Somnath Sikdar

Publication date 16 October 2012

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2010.09.001

zbMATH Keywords

parameterized complexitykernelizationfull degree spanning tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the directed degree-preserving spanning tree problem
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• scientific article; zbMATH DE number 1563034
• scientific article; zbMATH DE number 2081108

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 1563034 (Why is no real title available?)
• scientific article; zbMATH DE number 1420489 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• A linear vertex kernel for Maximum Internal Spanning Tree
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Easy problems for tree-decomposable graphs
• FPT algorithms and kernels for the directed k-leaf problem
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• Handbook of Graph Grammars and Computing by Graph Transformation
• Introduction to algorithms
• Minimum Leaf Out-Branching Problems
• On Local Search and Placement of Meters in Networks
• On finding directed trees with many leaves
• Parametrized complexity theory.
• Reducing to independent set structure -- the case of \(k\)-internal spanning tree
• Spanning directed trees with many leaves
• Treewidth. Computations and approximations
• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves

Cited in

(6)

• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• Fixed-parameter tractability results for full-degree spanning tree and its dual
• Complexity of the directed spanning cactus problem
• On the directed degree-preserving spanning tree problem
• On directed tree realizations of degree sets

This page was built for publication: On the directed full degree spanning tree problem

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