Minimum leaf out-branching and related problems

DOI10.1016/j.tcs.2009.03.036zbMath1343.68183OpenAlexW2084150181MaRDI QIDQ1035689

Igor Razgon, Gregory Gutin, 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

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) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (16)

Spotting Trees with Few Leaves ⋮ A 2k-vertex Kernel for Maximum Internal Spanning Tree ⋮ Mixing Color Coding-Related Techniques ⋮ A multivariate framework for weighted FPT algorithms ⋮ Linear kernels for outbranching problems in sparse digraphs ⋮ Beyond bidimensionality: parameterized subexponential algorithms on directed graphs ⋮ Representative families: a unified tradeoff-based approach ⋮ Sharp separation and applications to exact and parameterized algorithms ⋮ Digraph width measures in parameterized algorithmics ⋮ Designing deterministic polynomial-space algorithms by color-coding multivariate polynomials ⋮ Algorithms for \(k\)-internal out-branching and \(k\)-tree in bounded degree graphs ⋮ Unnamed Item ⋮ Cryptographic Enforcement of Information Flow Policies Without Public Information ⋮ Deeper local search for parameterized and approximation algorithms for maximum internal spanning tree ⋮ Kernelization: New Upper and Lower Bound Techniques ⋮ Acyclic Digraphs

Cites Work

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

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