Minimum leaf out-branching and related problems
From MaRDI portal
(Redirected from Publication:1035689)
directed graphsfixed-parameter tractableacyclic directed graphsout-branchingsminimum number of leaves
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
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)