On the directed full degree spanning tree problem

DOI10.1016/j.disopt.2010.09.001zbMath1248.90074MaRDI QIDQ456701

Venkatesh Raman, Saket Saurabh, Daniel Lokshtanov, 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 complexity; kernelization; full degree spanning tree

Mathematics Subject Classification ID

90C35: Programming involving graphs or networks

90C60: Abstract computational complexity for mathematical programming problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• Treewidth. Computations and approximations
• Parametrized complexity theory.
• Easy problems for tree-decomposable graphs
• Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual
• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• Minimum Leaf Out-Branching Problems
• A Linear Vertex Kernel for Maximum Internal Spanning Tree
• On Finding Directed Trees with Many Leaves
• Handbook of Graph Grammars and Computing by Graph Transformation
• On Local Search and Placement of Meters in Networks
• Spanning Directed Trees with Many Leaves
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves