Minimum leaf out-branching and related problems

DOI10.1016/J.TCS.2009.03.036MaRDI QIDQ1035689zbMATH OpenOpenAlexFDO

Authors G. Gutin, Igor Razgon, Eun Jung Kim

Publication date 4 November 2009

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2009.03.036

zbMATH Keywords

directed graphsfixed-parameter tractableacyclic directed graphsout-branchingsminimum number of leaves

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minimum Leaf Out-Branching Problems
• On complexity of minimum leaf out-branching problem
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Better Algorithms and Bounds for Directed Maximum Leaf Problems
• Spanning directed trees with many leaves

Cites work

• scientific article; zbMATH DE number 5485472 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
• Algorithms and Data Structures
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Digraphs
• Fixed-parameter complexity of minimum profile problems
• Graph-Theoretic Concepts in Computer Science
• Graph-Theoretic Concepts in Computer Science
• On Problems without Polynomial Kernels (Extended Abstract)
• Parameterized algorithmics for linear arrangement problems
• Parameterizing above Guaranteed Values: MaxSat and MaxCut
• Parametrized complexity theory.
• Reducing to independent set structure -- the case of \(k\)-internal spanning tree
• The linear arrangement problem parameterized above guaranteed value
• The minimum spanning strong subdigraph problem is fixed parameter tractable

Cited in

(19)

• Beyond bidimensionality: parameterized subexponential algorithms on directed graphs
• Kernelization: new upper and lower bound techniques
• Sharp separation and applications to exact and parameterized algorithms
• Minimum Leaf Out-Branching Problems
• Patching colors with tensors
• Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials
• On complexity of minimum leaf out-branching problem
• A \(2k\)-vertex kernel for maximum internal spanning tree
• Spotting trees with few leaves
• Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree
• Acyclic digraphs
• Cryptographic enforcement of information flow policies without public information
• Digraph width measures in parameterized algorithmics
• Out-branchings with maximal number of leaves or internal vertices: algorithmic results and open problems
• Mixing Color Coding-Related Techniques
• Linear kernels for outbranching problems in sparse digraphs
• A multivariate framework for weighted FPT algorithms
• Representative families: a unified tradeoff-based approach
• Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs

This page was built for publication: Minimum leaf out-branching and related problems

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