Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem

DOI10.1016/j.jcss.2010.01.001zbMath1210.05022OpenAlexW1980860702WikidataQ60488594 ScholiaQ60488594MaRDI QIDQ988577

J. Martínez

Publication date: 18 August 2010

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2010.01.001

zbMATH Keywords

out-branchingdivide-and-conquerinternal verticesout-tree

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Vertex degrees (05C07)

Related Items (23)

Spotting Trees with Few Leaves ⋮ Spotting Trees with Few Leaves ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ Mixing Color Coding-Related Techniques ⋮ Solving the maximum internal spanning tree problem on interval graphs in polynomial time ⋮ Parameterized algorithms for non-separating trees and branchings in digraphs ⋮ A simple linear time algorithm to solve the MIST problem on interval graphs ⋮ A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem ⋮ Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem ⋮ A multivariate framework for weighted FPT algorithms ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Exact and parameterized algorithms for \textsc{Max Internal Spanning Tree} ⋮ Representative families: a unified tradeoff-based approach ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Faster algorithms for finding and counting subgraphs ⋮ A Polynomial Time Algorithm for Finding a Spanning Tree with Maximum Number of Internal Vertices on Interval Graphs ⋮ An approximation algorithm for maximum internal spanning tree ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Unnamed Item ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Approximation algorithms for the maximum weight internal spanning tree problem ⋮ Algorithms for maximum internal spanning tree problem for some graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding paths of length \(k\) in \(O^{*}(2^k)\) time
• The number of trees
• Minimum Leaf Out-Branching Problems
• Faster Algebraic Algorithms for Path and Packing Problems
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Constant Time Generation of Rooted Trees
• Perfect Hashing and Probability
• Color-coding
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Algorithms and Data Structures

This page was built for publication: Algorithm for finding \(k\)-vertex out-trees and its application to \(k\)-internal out-branching problem