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

DOI10.1007/S00453-016-0166-3zbMATH Open1361.05133OpenAlexW2406276733MaRDI QIDQ527430FDOQ527430

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

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

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)

Cites Work

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