Minimum leaf out-branching and related problems
type: Item
instance of: scholarly article
title: Minimum leaf out-branching and related problems
zbMATH Open document ID: 1343.68183
author: G. Gutin
author: Igor Razgon
author: Eun Jung Kim
published in: Theoretical Computer Science
publication date: 2009-11-04T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5624938
zbMATH Keywords: directed graphs
zbMATH Keywords: out-branchings
zbMATH Keywords: minimum number of leaves
zbMATH Keywords: fixed-parameter tractable
zbMATH Keywords: acyclic directed graphs
MaRDI profile type: Publication
full work available at URL: j.tcs.2009.03.036
OpenAlex ID: W2084150181
cites work: Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
cites work: Digraphs
cites work: The minimum spanning strong subdigraph problem is fixed parameter tractable
cites work: On Problems without Polynomial Kernels (Extended Abstract)
cites work: Graph-Theoretic Concepts in Computer Science
cites work: Algorithm for Finding k-Vertex Out-trees and Its Application to k-Internal Out-branching Problem
cites work: Parameterized algorithmics for linear arrangement problems
cites work: Parametrized complexity theory.
cites work: The linear arrangement problem parameterized above guaranteed value
cites work: Fixed-parameter complexity of minimum profile problems
cites work: Q3549635
cites work: Parameterizing above Guaranteed Values: MaxSat and MaxCut
cites work: Q5710169
cites work: Algorithms and Data Structures
cites work: Q3369936
DOI: 10.1016/J.TCS.2009.03.036
description: scientific article; zbMATH DE number 5624938