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

DOI10.1016/j.jcss.2010.01.001zbMath1210.05022WikidataQ60488594 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-branching; divide-and-conquer; internal vertices; out-tree

Mathematics Subject Classification ID

05C05: Trees

05C85: Graph algorithms (graph-theoretic aspects)

05C07: Vertex degrees

Related Items

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

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