Minimum leaf out-branching and related problems

DOI10.1016/J.TCS.2009.03.036zbMATH Open1343.68183OpenAlexW2084150181MaRDI QIDQ1035689FDOQ1035689

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

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

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)

Cites Work

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

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)