Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem

DOI10.1007/978-3-642-02882-3_5zbMath1248.68370WikidataQ60488666 ScholiaQ60488666MaRDI QIDQ5323046

No author found.

Publication date: 23 July 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)

Related Items

On the directed full degree spanning tree problem ⋮ Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem ⋮ Minimum leaf out-branching and related problems ⋮ Out-branchings with Maximal Number of Leaves or Internal Vertices: Algorithmic Results and Open Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• The number of trees
• Minimum Leaf Out-Branching Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Divide-and-Color
• Constant Time Generation of Rooted Trees
• Perfect Hashing and Probability
• Color-coding
• Digraphs
• Algorithms and Data Structures