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

full degree spanning treekernelizationparameterized complexity

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

• \(\text{Kernel}(s)\) for problems with no kernel: on out-trees with many leaves
• A linear vertex kernel for Maximum Internal Spanning Tree
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Easy problems for tree-decomposable graphs
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• FPT algorithms and kernels for the directed k-leaf problem
• Handbook of Graph Grammars and Computing by Graph Transformation
• 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?)
• Introduction to algorithms
• Minimum Leaf Out-Branching Problems
• On finding directed trees with many leaves
• On Local Search and Placement of Meters in Networks
• 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

Cited in

(6)

• Complexity of the directed spanning cactus 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
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• 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)