On the directed full degree spanning tree problem

DOI10.1016/J.DISOPT.2010.09.001zbMATH Open1248.90074OpenAlexW2072755080MaRDI QIDQ456701FDOQ456701

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

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

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)

Cites Work

• Introduction to algorithms
• Parametrized complexity theory.
• Easy problems for tree-decomposable graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Treewidth. Computations and approximations
• Handbook of Graph Grammars and Computing by Graph Transformation
• FPT algorithms and kernels for the directed \(k\)-leaf problem
• On Local Search and Placement of Meters in Networks
• Spanning directed trees with many leaves
• Reducing to independent set structure -- the case of \(k\)-internal spanning tree
• A linear vertex kernel for Maximum Internal Spanning Tree
• On finding directed trees with many leaves
• Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem

Cited In (4)

• A Moderately Exponential Time Algorithm for Full Degree Spanning Tree
• 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

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)