Algorithms for k-internal out-branching and k-tree in bounded degree graphs

DOI10.1007/S00453-016-0166-3MaRDI QIDQ527430zbMATH OpenOpenAlexFDO

Authors Meirav Zehavi

Publication date 11 May 2017

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-016-0166-3

zbMATH Keywords

\(k\)-treeparameterized algorithmproper coloring\(k\)-internal out-branchingmultilinear detection

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Algorithms for \(k\)-internal out-branching
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• scientific article; zbMATH DE number 6784970
• Linear kernels for outbranching problems in sparse digraphs

Cites work

• scientific article; zbMATH DE number 3013308 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A \(2k\)-vertex kernel for maximum internal spanning tree
• A linear vertex kernel for maximum internal spanning tree
• A survey on algorithms for the maximum internal spanning tree and related problems
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem
• Algorithms for \(k\)-internal out-branching
• Color-coding
• Efficient computation of representative sets with applications in parameterized and exact algorithms
• Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree}
• Fast Polynomial-Space Algorithms Using Möbius Inversion: Improving on Steiner Tree and Related Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• Limits and Applications of Group Algebras for Parameterized Problems
• Minimum leaf out-branching and related problems
• Mixing Color Coding-Related Techniques
• Narrow sieves for parameterized paths and packings
• Reducing to independent set structure -- the case of \(k\)-internal spanning tree
• Representative families: a unified tradeoff-based approach
• Representative sets of product families
• Sharp separation and applications to exact and parameterized algorithms
• Some simplified NP-complete graph problems
• Spanning trees: A survey
• Spotting trees with few leaves
• -list vertex coloring in linear time

Cited in

(5)

• Patching colors with tensors
• Algorithms for \(k\)-internal out-branching
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem

This page was built for publication: Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs

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